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$-indexed(從 $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.