Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓
Statistiques

Пригадаємо алгоритм Тар'яна для знаходження точок зчленування (які також називають шарнірами) в неорієнтованому графі, псевдокод якого наведено в Алгоритмі 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$. Вони не можуть зрозуміти, чому алгоритм Тар'яна повинен по-різному обчислювати значення $\textit{low}[i]$, і можуть запам'ятати хибну версію алгоритму. Назвемо цю хибну версію алгоритмом Траяна, який наведено в Алгоритмі 2. Зауважте, що алгоритми Тар'яна та Траяна майже однакові, за винятком назв функцій та $4$ рядків з рядка $19$ до рядка $22$.

Задано неорієнтований зв'язний граф із $n$ вершинами та $m$ ребрами. Для кожної вершини $u$ визначте, чи існують вершина $v$ та $2$-вимірний масив $\textit{adj}$ ($\textit{adj}$ повинен подавати заданий граф), такі що $\textsc{Tarjan}(v, 0)$ та $\textsc{Trajan}(v, 0)$ дають різні результати на вершині $u$ (тобто алгоритм Тар'яна стверджує, що вершина $u$ є точкою зчленування, тоді як алгоритм Траяна — ні, або навпаки).

Вхідні дані

Вхідні дані містять декілька наборів вхідних даних. Перший рядок містить ціле число $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$.

Вихідні дані

Для кожного набору вхідних даних виведіть один рядок, що містить декілька цілих чисел, розділених одним пробілом, у порядку зростання. Кожне число — це вершина, на якій алгоритми Тар'яна та Траяна можуть дати різні результати. Якщо таких вершин немає, виведіть натомість в одному рядку 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.