Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Zorluk: [göster] Hack'lenebilir ✓
İstatistikler

Ingat kembali Algoritma Tarjan untuk menghitung titik artikulasi (disebut juga simpul potong) pada sebuah graf tak berarah, yang kode semunya ditunjukkan pada Algoritma 1.

Algorithm 1 The Correct Tarjan Algorithm
 1: function TARJAN(i, d)
 2:     visited[i] <- true
 3:     depth[i] <- d
 4:     low[i] <- d
 5:     childCount <- 0
 6:     isArticulation <- false
 7:
 8:     for each j in adj[i] do
 9:         if j = parent[i] then
10:             continue
11:         end if
12:         if not visited[j] then
13:             parent[j] <- i
14:             TARJAN(j, d + 1)
15:             childCount <- childCount + 1
16:             if low[j] >= depth[i] then
17:                 isArticulation <- true
18:             end if
19:             low[i] <- min(low[i], low[j])
20:         else
21:             low[i] <- min(low[i], depth[j])
22:         end if
23:     end for
24:     if (parent[i] != null and isArticulation)
        or (parent[i] = null and childCount > 1)
        then
25:         Output i as articulation point
26:     end if
27: end function
Algorithm 2 The Incorrect Trajan Algorithm
 1: function TRAJAN(i, d)
 2:     visited[i] <- true
 3:     depth[i] <- d
 4:     low[i] <- d
 5:     childCount <- 0
 6:     isArticulation <- false
 7:
 8:     for each j in adj[i] do
 9:         if j = parent[i] then
10:             continue
11:         end if
12:         if not visited[j] then
13:             parent[j] <- i
14:             TRAJAN(j, d + 1)
15:             childCount <- childCount + 1
16:             if low[j] >= depth[i] then
17:                 isArticulation <- true
18:             end if
19:         end if
20:         low[i] <- min(low[i], low[j])
21:
22:
23:     end for
24:     if (parent[i] != null and isArticulation)
        or (parent[i] = null and childCount > 1)
        then
25:         Output i as articulation point
26:     end if
27: end function

Perhatikan bahwa dalam kode semu tersebut, $\textit{adj}[i]$ adalah larik yang berisi semua simpul yang bertetangga dengan simpul $i$, $\textit{parent}$ adalah larik yang nilai awal setiap elemennya adalah $\text{null}$, dan $\textit{visited}$ adalah larik yang nilai awal setiap elemennya adalah $\text{false}$.

Sebagian siswa mungkin mengalami kesulitan memahami algoritma ini, terutama dari baris $19$ hingga baris $22$. Mereka tidak memahami mengapa Algoritma Tarjan perlu menghitung nilai $\textit{low}[i]$ secara berbeda, dan mereka mungkin mengingat versi yang salah dari algoritma tersebut. Mari kita sebut versi yang salah ini sebagai Algoritma Trajan, yang ditunjukkan pada Algoritma 2. Perhatikan bahwa algoritma Tarjan dan Trajan hampir sama persis, kecuali nama fungsi serta $4$ baris dari baris $19$ hingga baris $22$.

Diberikan sebuah graf terhubung tak berarah dengan $n$ simpul dan $m$ sisi, untuk setiap simpul $u$ tentukan apakah terdapat sebuah simpul $v$ dan sebuah larik $2$ dimensi $\textit{adj}$ ($\textit{adj}$ harus merepresentasikan graf yang diberikan) sedemikian sehingga $\textsc{Tarjan}(v, 0)$ dan $\textsc{Trajan}(v, 0)$ menghasilkan keluaran yang berbeda pada simpul $u$ (artinya, Algoritma Tarjan menyatakan bahwa simpul $u$ adalah titik artikulasi sedangkan Algoritma Trajan tidak, atau sebaliknya).

Masukan

Terdapat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$) yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat $n$ dan $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) yang menyatakan banyaknya simpul dan sisi pada graf yang diberikan.

Untuk $m$ baris berikutnya, baris ke-$i$ berisi dua bilangan bulat $u_i$ dan $v_i$ ($1 \le u_i, v_i \le n$) yang menyatakan bahwa terdapat sisi yang menghubungkan simpul $u_i$ dan $v_i$ di dalam graf.

Dijamin bahwa graf yang diberikan terhubung serta tidak memiliki gelung (self-loop) maupun sisi ganda. Selain itu, baik jumlah nilai $n$ maupun jumlah nilai $m$ dari seluruh kasus uji tidak akan melebihi $10^6$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi sejumlah bilangan bulat yang dipisahkan oleh satu spasi dalam urutan menaik. Setiap bilangan bulat adalah simpul di mana algoritma Tarjan dan Trajan dapat menghasilkan keluaran yang berbeda. Jika tidak ada simpul demikian, keluarkan Empty dalam satu baris sebagai gantinya.

Contoh

Contoh Masukan 1

2
9 12
1 3
2 3
1 2
3 6
6 9
9 3
4 6
5 6
4 5
7 9
8 9
7 8
2 1
1 2

Contoh Keluaran 1

3 6 9
Empty

Catatan

Untuk kasus uji contoh pertama:

  • Untuk $u = 3$, tinjau $v = 1$ dan $\textit{adj} = [[3, 2], [3, 1], [1, 2, 6, 9], [6, 5], [6, 4], [4, 5, 3, 9], [9, 8], [9, 7], [7, 8, 3, 6]]$.
  • Untuk $u = 6$, tinjau $v = 4$ dan $\textit{adj} = [[2, 3], [1, 3], [9, 6, 2, 1], [6, 5], [6, 4], [4, 5, 3, 9], [9, 8], [9, 7], [7, 8, 3, 6]]$.
  • Untuk $u = 9$, tinjau $v = 7$ dan $\textit{adj} = [[2, 3], [1, 3], [9, 6, 2, 1], [5, 6], [4, 6], [9, 3, 5, 4], [9, 8], [9, 7], [7, 8, 3, 6]]$.

Perhatikan bahwa semua $\textit{adj}$ pada penjelasan di atas menggunakan indeks berbasis $1$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.