Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 난이도: [표시] 해킹 가능 ✓
통계

無向グラフにおける関節点(切断点とも呼ばれます)を求める 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 であることに注意してください。

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.