Husk Tarjans algoritme for å beregne artikulasjonspunktene (også kalt kuttnoder) i en urettet graf, hvis pseudokode er vist i Algoritme 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
Merk at i pseudokoden er $\textit{adj}[i]$ tabellen som inneholder alle noder som er naboer til node $i$, $\textit{parent}$ er en tabell der startverdien til hvert element er $\text{null}$, og $\textit{visited}$ er en tabell der startverdien til hvert element er $\text{false}$.
Noen studenter kan ha vanskeligheter med å forstå denne algoritmen, spesielt fra linje $19$ til linje $22$. De forstår ikke hvorfor Tarjans algoritme må beregne verdien av $\textit{low}[i]$ på ulike måter, og kan komme til å huske en feilaktig versjon av algoritmen. La oss kalle denne feilaktige versjonen av algoritmen for Trajans algoritme, som er vist i Algoritme 2. Legg merke til at Tarjan- og Trajan-algoritmene er nesten helt like, bortsett fra funksjonsnavnene og de $4$ linjene fra linje $19$ til linje $22$.
Gitt en urettet sammenhengende graf med $n$ noder og $m$ kanter, avgjør for hver node $u$ om det finnes en node $v$ og en $2$-dimensjonal tabell $\textit{adj}$ ($\textit{adj}$ må representere den gitte grafen) slik at $\textsc{Tarjan}(v, 0)$ og $\textsc{Trajan}(v, 0)$ gir ulike resultater på node $u$ (det vil si at Tarjans algoritme fastslår at node $u$ er et artikulasjonspunkt mens Trajans algoritme ikke gjør det, eller omvendt).
Inndata
Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^4$) som angir antall testtilfeller. For hvert testtilfelle:
Den første linjen inneholder to heltall $n$ og $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) som angir antall noder og kanter i den gitte grafen.
I de følgende $m$ linjene inneholder den $i$-te linjen to heltall $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$) som angir at det er en kant som forbinder nodene $u_i$ og $v_i$ i grafen.
Det garanteres at den gitte grafen er sammenhengende og at det ikke finnes løkker eller multiple kanter. Dessuten vil verken summen av $n$ eller summen av $m$ over alle testtilfellene overstige $10^6$.
Utdata
For hvert testtilfelle skal du skrive ut én linje som inneholder noen heltall atskilt med ett mellomrom i stigende rekkefølge. Hvert heltall er en node der Tarjan- og Trajan-algoritmen kan gi ulike resultater. Hvis det ikke finnes noen slike noder, skriv ut Empty på én linje i stedet.
Eksempel
Eksempelinndata 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
Eksempelutdata 1
3 6 9 Empty
Merk
For det første eksempeltesttilfellet:
- For $u = 3$, betrakt $v = 1$ og $\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]]$.
- For $u = 6$, betrakt $v = 4$ og $\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]]$.
- For $u = 9$, betrakt $v = 7$ og $\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]]$.
Merk at alle $\textit{adj}$ i forklaringen er $1$-indekserte.