Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Zorluk: [göster] Hack'lenebilir ✓
İstatistikler

Przypomnijmy algorytm Tarjana służący do wyznaczania punktów artykulacji (nazywanych również wierzchołkami rozspajającymi) w grafie nieskierowanym, którego pseudokod przedstawiono w Algorytmie 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

Zauważ, że w pseudokodzie $\textit{adj}[i]$ jest tablicą zawierającą wszystkie wierzchołki sąsiadujące z wierzchołkiem $i$, $\textit{parent}$ jest tablicą, w której wartością początkową każdego elementu jest $\text{null}$, natomiast $\textit{visited}$ jest tablicą, w której wartością początkową każdego elementu jest $\text{false}$.

Niektórzy studenci mogą mieć trudności ze zrozumieniem tego algorytmu, zwłaszcza od wiersza $19$ do wiersza $22$. Nie rozumieją oni, dlaczego algorytm Tarjana musi obliczać wartość $\textit{low}[i]$ w różny sposób, i mogą zapamiętać niepoprawną wersję algorytmu. Nazwijmy tę niepoprawną wersję algorytmem Trajana, przedstawionym w Algorytmie 2. Zwróć uwagę, że algorytmy Tarjana i Trajana są niemal identyczne, z wyjątkiem nazw funkcji oraz $4$ wierszy od wiersza $19$ do wiersza $22$.

Dla danego nieskierowanego grafu spójnego o $n$ wierzchołkach i $m$ krawędziach, dla każdego wierzchołka $u$ rozstrzygnij, czy istnieją wierzchołek $v$ oraz $2$-wymiarowa tablica $\textit{adj}$ ($\textit{adj}$ musi reprezentować dany graf) takie, że wywołania $\textsc{Tarjan}(v, 0)$ oraz $\textsc{Trajan}(v, 0)$ dają różne wyniki dla wierzchołka $u$ (to znaczy algorytm Tarjana uznaje wierzchołek $u$ za punkt artykulacji, podczas gdy algorytm Trajana nie, lub odwrotnie).

Wejście

Wejście zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$) oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) oznaczające liczbę wierzchołków i krawędzi w danym grafie.

W kolejnych $m$ wierszach $i$-ty wiersz zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n$) oznaczające, że w grafie istnieje krawędź łącząca wierzchołki $u_i$ oraz $v_i$.

Gwarantuje się, że dany graf jest spójny oraz nie zawiera pętli ani krawędzi wielokrotnych. Ponadto ani suma $n$, ani suma $m$ po wszystkich przypadkach testowych nie przekroczy $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający pewne liczby całkowite oddzielone pojedynczą spacją w porządku rosnącym. Każda liczba całkowita to wierzchołek, dla którego algorytmy Tarjana i Trajana mogą dać różne wyniki. Jeśli takie wierzchołki nie istnieją, wypisz zamiast tego w jednym wierszu Empty.

Przykład

Przykładowe wejście 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

Przykładowe wyjście 1

3 6 9
Empty

Uwaga

Dla pierwszego przykładowego przypadku testowego:

  • Dla $u = 3$ rozważ $v = 1$ oraz $\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]]$.
  • Dla $u = 6$ rozważ $v = 4$ oraz $\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]]$.
  • Dla $u = 9$ rozważ $v = 7$ oraz $\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]]$.

Zauważ, że wszystkie tablice $\textit{adj}$ w wyjaśnieniu są indeksowane od $1$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.