回顧用於計算無向圖中的關節點(亦稱為割點)的 Tarjan 演算法,其虛擬碼如演算法 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
請注意,在虛擬碼中,$\textit{adj}[i]$ 是包含所有與頂點 $i$ 相鄰之頂點的陣列,$\textit{parent}$ 是每個元素初始值皆為 $\text{null}$ 的陣列,而 $\textit{visited}$ 是每個元素初始值皆為 $\text{false}$ 的陣列。
有些學生可能很難理解這個演算法,特別是從第 $19$ 行到第 $22$ 行。他們無法理解為什麼 Tarjan 演算法 需要以不同的方式計算 $\textit{low}[i]$ 的值,因此腦海中可能會記成一個錯誤版本的演算法。我們將這個錯誤版本的演算法稱為 Trajan 演算法,如演算法 2 所示。請注意,Tarjan 與 Trajan 演算法除了函式名稱以及從第 $19$ 行到第 $22$ 行的 $4$ 行之外,幾乎完全相同。
給定一個具有 $n$ 個頂點與 $m$ 條邊的無向連通圖,請對每個頂點 $u$ 判斷是否存在一個頂點 $v$ 以及一個 $2$ 維陣列 $\textit{adj}$($\textit{adj}$ 必須表示給定的圖),使得 $\textsc{Tarjan}(v, 0)$ 與 $\textsc{Trajan}(v, 0)$ 在頂點 $u$ 上產生不同的結果(也就是說,Tarjan 演算法 判定頂點 $u$ 是關節點而 Trajan 演算法 判定不是,或者相反)。
輸入格式
輸入包含多組測試資料。輸入的第一行包含一個整數 $T$ ($1 \le T \le 10^4$),表示測試資料的組數。對於每組測試資料:
第一行包含兩個整數 $n$ 和 $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$),表示給定圖中的頂點數和邊數。
接下來的 $m$ 行中,第 $i$ 行包含兩個整數 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$),表示圖中有一條連接頂點 $u_i$ 和 $v_i$ 的邊。
保證給定的圖是連通的,且沒有自環或重邊。此外,所有測試資料的 $n$ 總和與 $m$ 總和皆不會超過 $10^6$。
輸出格式
對於每組測試資料輸出一行,包含若干個以一個空格分隔且按遞增順序排列的整數。每個整數代表一個 Tarjan 與 Trajan 演算法可能產生不同結果的頂點。若不存在這樣的頂點,請改為在一行中輸出 Empty。
範例
範例輸入 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
範例輸出 1
3 6 9 Empty
說明
對於第一組範例測試資料:
- 對於 $u = 3$,考慮 $v = 1$ 以及 $\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]]$。
- 對於 $u = 6$,考慮 $v = 4$ 以及 $\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]]$。
- 對於 $u = 9$,考慮 $v = 7$ 以及 $\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]]$。
請注意,說明中的所有 $\textit{adj}$ 皆為 $1$-indexed(從 $1$ 開始編號)。