Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

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$.

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.