Universal Cup Judging System

Universal Cup

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

Påminn dig om Tarjans algoritm för att beräkna artikulationspunkterna (även kallade skärningshörn) i en oriktad graf, vars pseudokod visas i Algoritm 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

Observera att i pseudokoden är $\textit{adj}[i]$ arrayen som innehåller alla hörn som är grannar till hörn $i$, $\textit{parent}$ är en array där startvärdet för varje element är $\text{null}$, och $\textit{visited}$ är en array där startvärdet för varje element är $\text{false}$.

Vissa studenter kan ha svårt att förstå denna algoritm, särskilt från rad $19$ till rad $22$. De förstår inte varför Tarjans algoritm behöver beräkna värdet på $\textit{low}[i]$ på olika sätt, och kan därför lägga en felaktig version av algoritmen på minnet. Låt oss kalla denna felaktiga version av algoritmen för Trajans algoritm, vilken visas i Algoritm 2. Lägg märke till att Tarjans och Trajans algoritmer är nästan identiska, bortsett från funktionsnamnen och de $4$ raderna från rad $19$ till rad $22$.

Givet en oriktad sammanhängande graf med $n$ hörn och $m$ kanter, avgör för varje hörn $u$ om det finns ett hörn $v$ och en $2$-dimensionell array $\textit{adj}$ ($\textit{adj}$ måste representera den givna grafen) sådana att $\textsc{Tarjan}(v, 0)$ och $\textsc{Trajan}(v, 0)$ ger olika resultat för hörnet $u$ (det vill säga att Tarjans algoritm anger att hörnet $u$ är en artikulationspunkt medan Trajans algoritm inte gör det, eller omvänt).

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 10^4$) som anger antalet testfall. För varje testfall:

Den första raden innehåller två heltal $n$ och $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) som anger antalet hörn och kanter i den givna grafen.

På de följande $m$ raderna innehåller den $i$-te raden två heltal $u_i$ och $v_i$ ($1 \le u_i, v_i \le n$) som anger att det finns en kant som förbinder hörnen $u_i$ och $v_i$ i grafen.

Det garanteras att den givna grafen är sammanhängande och att det inte finns några öglor eller multipla kanter. Dessutom överstiger varken summan av $n$ eller summan av $m$ över alla testfall $10^6$.

Utdata

För varje testfall, skriv ut en rad som innehåller ett antal heltal separerade med ett mellanslag i stigande ordning. Varje heltal är ett hörn där Tarjans och Trajans algoritm kan ge olika resultat. Om det inte finns några sådana hörn, skriv istället ut Empty på en rad.

Exempel

Exempelindata 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

Exempelutdata 1

3 6 9
Empty

Förklaring

För det första exempeltestfallet:

  • För $u = 3$, betrakta $v = 1$ och $\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]]$.
  • För $u = 6$, betrakta $v = 4$ och $\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]]$.
  • För $u = 9$, betrakta $v = 7$ och $\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]]$.

Observera att alla $\textit{adj}$ i förklaringen är $1$-indexerade.

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.