Universal Cup Judging System

Universal Cup

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

Erinnern wir uns an den Tarjan-Algorithmus zur Berechnung der Artikulationspunkte (auch Schnittknoten genannt) in einem ungerichteten Graphen, dessen Pseudocode in Algorithmus 1 dargestellt ist.

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

Beachte, dass im Pseudocode $\textit{adj}[i]$ das Array ist, das alle zu Knoten $i$ benachbarten Knoten enthält, $\textit{parent}$ ein Array ist, in dem der Anfangswert jedes Elements $\text{null}$ ist, und $\textit{visited}$ ein Array ist, in dem der Anfangswert jedes Elements $\text{false}$ ist.

Einige Studierende haben Schwierigkeiten, diesen Algorithmus zu verstehen, insbesondere von Zeile $19$ bis Zeile $22$. Sie verstehen nicht, warum der Tarjan-Algorithmus den Wert von $\textit{low}[i]$ unterschiedlich berechnen muss, und merken sich möglicherweise eine falsche Version des Algorithmus. Nennen wir diese falsche Version den Trajan-Algorithmus, der in Algorithmus 2 dargestellt ist. Beachte, dass der Tarjan- und der Trajan-Algorithmus bis auf die Funktionsnamen und die $4$ Zeilen von Zeile $19$ bis Zeile $22$ fast identisch sind.

Gegeben ist ein ungerichteter zusammenhängender Graph mit $n$ Knoten und $m$ Kanten. Bestimme für jeden Knoten $u$, ob es einen Knoten $v$ und ein $2$-dimensionales Array $\textit{adj}$ gibt ($\textit{adj}$ muss den gegebenen Graphen darstellen), sodass $\textsc{Tarjan}(v, 0)$ und $\textsc{Trajan}(v, 0)$ für den Knoten $u$ unterschiedliche Ergebnisse liefern (das heißt, der Tarjan-Algorithmus gibt an, dass Knoten $u$ ein Artikulationspunkt ist, während der Trajan-Algorithmus dies nicht tut, oder umgekehrt).

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), die die Anzahl der Knoten und Kanten im gegebenen Graphen angeben.

In den folgenden $m$ Zeilen enthält die $i$-te Zeile zwei ganze Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le n$), was bedeutet, dass es im Graphen eine Kante zwischen den Knoten $u_i$ und $v_i$ gibt.

Es wird garantiert, dass der gegebene Graph zusammenhängend ist und weder Selbstschleifen noch Mehrfachkanten enthält. Außerdem überschreiten weder die Summe von $n$ noch die Summe von $m$ über alle Testfälle hinweg $10^6$.

Ausgabe

Gib für jeden Testfall eine Zeile mit einigen durch jeweils ein Leerzeichen getrennten ganzen Zahlen in aufsteigender Reihenfolge aus. Jede ganze Zahl ist ein Knoten, bei dem der Tarjan- und der Trajan-Algorithmus unterschiedliche Ergebnisse liefern können. Falls es keine solchen Knoten gibt, gib stattdessen in einer Zeile Empty aus.

Beispiel

Beispieleingabe 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

Beispielausgabe 1

3 6 9
Empty

Hinweis

Für den ersten Beispieltestfall:

  • Betrachte für $u = 3$ die Wahl $v = 1$ und $\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]]$.
  • Betrachte für $u = 6$ die Wahl $v = 4$ und $\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]]$.
  • Betrachte für $u = 9$ die Wahl $v = 7$ und $\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]]$.

Beachte, dass alle $\textit{adj}$ in der Erklärung $1$-indiziert sind.

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.