Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 難易度: [表示] ハック可能 ✓
統計

무방향 그래프에서 단절점(articulation point 또는 cut vertex)을 구하는 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$에 대해 $\textsc{Tarjan}(v, 0)$과 $\textsc{Trajan}(v, 0)$이 정점 $u$에서 서로 다른 결과를 내도록 하는 정점 $v$와 $2$차원 배열 $\textit{adj}$($\textit{adj}$는 주어진 그래프를 나타내야 함)가 존재하는지 판별하십시오(즉, 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$를 잇는 간선이 있음을 나타내는 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n$)가 주어집니다.

주어진 그래프는 연결 그래프이며 자기 루프나 다중 간선이 없음이 보장됩니다. 또한 모든 테스트 케이스에서 $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$-인덱스($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.