Бағытталмаған графтағы буын нүктелерін (қию төбелері деп те аталады) есептеуге арналған Тарьян алгоритмін еске түсірейік, оның псевдокоды 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
Псевдокодта $\textit{adj}[i]$ — $i$ төбесімен көршілес барлық төбелерді қамтитын массив, $\textit{parent}$ — әрбір элементінің бастапқы мәні $\text{null}$ болатын массив, ал $\textit{visited}$ — әрбір элементінің бастапқы мәні $\text{false}$ болатын массив екеніне назар аударыңыз.
Кейбір студенттерге бұл алгоритмді, әсіресе $19$-жолдан $22$-жолға дейінгі бөлігін түсіну қиынға соғуы мүмкін. Олар Тарьян алгоритмі неліктен $\textit{low}[i]$ мәнін әртүрлі есептеуі керек екенін түсінбей, алгоритмнің қате нұсқасын есте сақтап қалуы мүмкін. Алгоритмнің бұл қате нұсқасын Траян алгоритмі деп атайық, ол 2-алгоритмде көрсетілген. Тарьян мен Траян алгоритмдері функция атаулары мен $19$-жолдан $22$-жолға дейінгі $4$ жолды қоспағанда, бірдей дерлік екенін байқаңыз.
$n$ төбесі мен $m$ қыры бар бағытталмаған байланысқан граф берілген. Әрбір $u$ төбесі үшін $\textsc{Tarjan}(v, 0)$ және $\textsc{Trajan}(v, 0)$ шақырулары $u$ төбесінде әртүрлі нәтиже беретіндей $v$ төбесі мен $2$-өлшемді $\textit{adj}$ массиві ($\textit{adj}$ берілген графты сипаттауы тиіс) табылатынын анықтаңыз (яғни Тарьян алгоритмі $u$ төбесін буын нүктесі деп есептейді, ал Траян алгоритмі олай есептемейді, немесе керісінше).
Кіріс деректер
Бірнеше тест жағдайлары бар. Кірістің бірінші жолында тест жағдайларының санын білдіретін бүтін сан $T$ ($1 \le T \le 10^4$) берілген. Әрбір тест жағдайы үшін:
Бірінші жолда берілген графтағы төбелер мен қырлар санын білдіретін екі бүтін сан $n$ және $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) берілген.
Келесі $m$ жолдың $i$-ші жолында графта $u_i$ мен $v_i$ төбелерін қосатын қыр бар екенін білдіретін екі бүтін сан $u_i$ және $v_i$ ($1 \le u_i, v_i \le n$) берілген.
Берілген графтың байланысқан екеніне және онда ілмектер мен еселі қырлар жоқ екеніне кепілдік беріледі. Сондай-ақ барлық тест жағдайлары бойынша $n$ қосындысы да, $m$ қосындысы да $10^6$-нен аспайды.
Шығыс деректер
Әрбір тест жағдайы үшін өсу ретімен бір бос орын арқылы бөлінген бірнеше бүтін саннан тұратын бір жол шығарыңыз. Әрбір бүтін сан — Тарьян мен Траян алгоритмдері әртүрлі нәтиже беруі мүмкін төбе. Егер ондай төбелер болмаса, оның орнына бір жолға Empty деп шығарыңыз.
Мысал
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
1-мысал шығысы
3 6 9 Empty
Ескертпе
Бірінші мысалдағы тест жағдайы үшін:
- $u = 3$ үшін $v = 1$ және $\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]]$ қарастырыңыз.
- $u = 6$ үшін $v = 4$ және $\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]]$ қарастырыңыз.
- $u = 9$ үшін $v = 7$ және $\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]]$ қарастырыңыз.
Түсіндірмедегі барлық $\textit{adj}$ массивтері $1$-ден бастап индекстелетініне назар аударыңыз.