無向グラフにおける関節点(切断点とも呼ばれます)を求める 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$) が与えられます。各テストケースについて:
最初の行には、与えられたグラフの頂点数と辺数を表す $2$ つの整数 $n$ と $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) が与えられます。
続く $m$ 行のうち $i$ 行目には、グラフ内で頂点 $u_i$ と $v_i$ を結ぶ辺が存在することを表す $2$ つの整数 $u_i$ と $v_i$ ($1 \le u_i, v_i \le n$) が与えられます。
与えられたグラフは連結であり、自己ループや多重辺を持たないことが保証されます。また、すべてのテストケースにおける $n$ の総和および $m$ の総和はどちらも $10^6$ を超えません。
出力
各テストケースについて、いくつかの整数を昇順に $1$ つの空白で区切って $1$ 行に出力してください。各整数は、Tarjan と Trajan のアルゴリズムが異なる結果を出力し得る頂点です。そのような頂点が存在しない場合は、代わりに $1$ 行に 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 であることに注意してください。