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$.