Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

回顧用嚟計算無向圖入面嘅割點(又稱為關節點)嘅 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$ 開始編號嘅。

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.