Rifjum upp reiknirit Tarjans til að reikna út liðhnúta (einnig kallaðir skurðhnútar) í óstefndu neti, en sauðakóði þess er sýndur í Reikniriti 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
Athugið að í sauðakóðanum er $\textit{adj}[i]$ fylkið sem inniheldur alla hnúta sem eru aðlægir hnút $i$, $\textit{parent}$ er fylki þar sem upphafsgildi hvers staks er $\text{null}$, og $\textit{visited}$ er fylki þar sem upphafsgildi hvers staks er $\text{false}$.
Sumir nemendur eiga erfitt með að skilja þetta reiknirit, sérstaklega frá línu $19$ til línu $22$. Þeir skilja ekki hvers vegna reiknirit Tarjans þarf að reikna gildið á $\textit{low}[i]$ á ólíkan hátt og kunna því að leggja ranga útgáfu reikniritsins á minnið. Köllum þessa röngu útgáfu reiknirit Trajans, sem sýnt er í Reikniriti 2. Takið eftir að reiknirit Tarjans og Trajans eru nánast eins, fyrir utan nöfn fallanna og línurnar $4$ frá línu $19$ til línu $22$.
Gefið er óstefnt samanhangandi net með $n$ hnútum og $m$ leggjum. Ákvarðið fyrir hvern hnút $u$ hvort til sé hnútur $v$ og $2$-vítt fylki $\textit{adj}$ ($\textit{adj}$ verður að tákna gefna netið) þannig að $\textsc{Tarjan}(v, 0)$ og $\textsc{Trajan}(v, 0)$ skili ólíkum niðurstöðum fyrir hnútinn $u$ (þ.e.a.s. reiknirit Tarjans segir að hnútur $u$ sé liðhnútur á meðan reiknirit Trajans gerir það ekki, eða öfugt).
Inntak
Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 10^4$) sem táknar fjölda prófunartilvika. Fyrir hvert prófunartilvik:
Fyrsta línan inniheldur tvær heiltölur $n$ og $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) sem tákna fjölda hnúta og leggja í gefna netinu.
Í næstu $m$ línum inniheldur $i$-ta línan tvær heiltölur $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$) sem tákna að leggur tengi hnútana $u_i$ og $v_i$ í netinu.
Tryggt er að gefna netið sé samanhangandi og að engar sjálfslykkjur eða margfaldir leggir séu til staðar. Einnig fer hvorki summa $n$ né summa $m$ yfir öll prófunartilvik fram úr $10^6$.
Úttak
Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur nokkrar heiltölur aðskildar með einu bili í hækkandi röð. Hver heiltala er hnútur þar sem reiknirit Tarjans og Trajans geta skilað ólíkum niðurstöðum. Ef engir slíkir hnútar eru til skal prenta Empty í einni línu í staðinn.
Dæmi
Sýnidæmi 1 — Inntak
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
Sýnidæmi 1 — Úttak
3 6 9 Empty
Athugasemd
Fyrir fyrsta prófunartilvikið í sýnidæminu:
- Fyrir $u = 3$ má skoða $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]]$.
- Fyrir $u = 6$ má skoða $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]]$.
- Fyrir $u = 9$ má skoða $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]]$.
Athugið að öll $\textit{adj}$ í skýringunni eru $1$-vísuð ($1$-indexed).