Ricordiamo l'algoritmo di Tarjan per calcolare i punti di articolazione (chiamati anche vertici di taglio) in un grafo non orientato, il cui pseudocodice è mostrato nell'Algoritmo 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
Si noti che nello pseudocodice $\textit{adj}[i]$ è l'array contenente tutti i vertici adiacenti al vertice $i$, $\textit{parent}$ è un array in cui il valore iniziale di ciascun elemento è $\text{null}$, e $\textit{visited}$ è un array in cui il valore iniziale di ciascun elemento è $\text{false}$.
Alcuni studenti possono avere difficoltà a comprendere questo algoritmo, specialmente dalla riga $19$ alla riga $22$. Non riescono a capire perché l'algoritmo di Tarjan debba calcolare il valore di $\textit{low}[i]$ in modo diverso, e potrebbero tenere a mente una versione errata dell'algoritmo. Chiamiamo questa versione errata algoritmo di Trajan, mostrata nell'Algoritmo 2. Si noti che gli algoritmi di Tarjan e di Trajan sono quasi identici, ad eccezione dei nomi delle funzioni e delle $4$ righe dalla riga $19$ alla riga $22$.
Dato un grafo connesso non orientato con $n$ vertici e $m$ archi, per ogni vertice $u$ determina se esistono un vertice $v$ e un array $2$-dimensionale $\textit{adj}$ ($\textit{adj}$ deve rappresentare il grafo dato) tali che $\textsc{Tarjan}(v, 0)$ e $\textsc{Trajan}(v, 0)$ producano risultati diversi sul vertice $u$ (vale a dire che l'algoritmo di Tarjan afferma che il vertice $u$ è un punto di articolazione mentre l'algoritmo di Trajan no, o viceversa).
Input
Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^4$) che indica il numero di casi di test. Per ogni caso di test:
La prima riga contiene due interi $n$ e $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) che indicano il numero di vertici e di archi nel grafo dato.
Per le successive $m$ righe, la $i$-esima riga contiene due interi $u_i$ e $v_i$ ($1 \le u_i, v_i \le n$) che indicano che c'è un arco che collega i vertici $u_i$ e $v_i$ nel grafo.
È garantito che il grafo dato è connesso e che non ci sono cappi o archi multipli. Inoltre, né la somma di $n$ né la somma di $m$ su tutti i casi di test supereranno $10^6$.
Output
Per ogni caso di test stampa una riga contenente alcuni interi separati da uno spazio in ordine crescente. Ogni intero è un vertice su cui gli algoritmi di Tarjan e di Trajan possono produrre risultati diversi. Se non esistono tali vertici, stampa invece Empty su una riga.
Esempio
Input di esempio 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
Output di esempio 1
3 6 9 Empty
Note
Per il primo caso di test di esempio:
- Per $u = 3$ considera $v = 1$ e $\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]]$.
- Per $u = 6$ considera $v = 4$ e $\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]]$.
- Per $u = 9$ considera $v = 7$ e $\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]]$.
Si noti che tutti gli $\textit{adj}$ nella spiegazione sono indicizzati a partire da $1$.