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.