Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓
Statistiques

Husk Tarjans algoritme for å beregne artikulasjonspunktene (også kalt kuttnoder) i en urettet graf, hvis pseudokode er vist i Algoritme 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

Merk at i pseudokoden er $\textit{adj}[i]$ tabellen som inneholder alle noder som er naboer til node $i$, $\textit{parent}$ er en tabell der startverdien til hvert element er $\text{null}$, og $\textit{visited}$ er en tabell der startverdien til hvert element er $\text{false}$.

Noen studenter kan ha vanskeligheter med å forstå denne algoritmen, spesielt fra linje $19$ til linje $22$. De forstår ikke hvorfor Tarjans algoritme må beregne verdien av $\textit{low}[i]$ på ulike måter, og kan komme til å huske en feilaktig versjon av algoritmen. La oss kalle denne feilaktige versjonen av algoritmen for Trajans algoritme, som er vist i Algoritme 2. Legg merke til at Tarjan- og Trajan-algoritmene er nesten helt like, bortsett fra funksjonsnavnene og de $4$ linjene fra linje $19$ til linje $22$.

Gitt en urettet sammenhengende graf med $n$ noder og $m$ kanter, avgjør for hver node $u$ om det finnes en node $v$ og en $2$-dimensjonal tabell $\textit{adj}$ ($\textit{adj}$ må representere den gitte grafen) slik at $\textsc{Tarjan}(v, 0)$ og $\textsc{Trajan}(v, 0)$ gir ulike resultater på node $u$ (det vil si at Tarjans algoritme fastslår at node $u$ er et artikulasjonspunkt mens Trajans algoritme ikke gjør det, eller omvendt).

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^4$) som angir antall testtilfeller. For hvert testtilfelle:

Den første linjen inneholder to heltall $n$ og $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) som angir antall noder og kanter i den gitte grafen.

I de følgende $m$ linjene inneholder den $i$-te linjen to heltall $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$) som angir at det er en kant som forbinder nodene $u_i$ og $v_i$ i grafen.

Det garanteres at den gitte grafen er sammenhengende og at det ikke finnes løkker eller multiple kanter. Dessuten vil verken summen av $n$ eller summen av $m$ over alle testtilfellene overstige $10^6$.

Utdata

For hvert testtilfelle skal du skrive ut én linje som inneholder noen heltall atskilt med ett mellomrom i stigende rekkefølge. Hvert heltall er en node der Tarjan- og Trajan-algoritmen kan gi ulike resultater. Hvis det ikke finnes noen slike noder, skriv ut Empty på én linje i stedet.

Eksempel

Eksempelinndata 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

Eksempelutdata 1

3 6 9
Empty

Merk

For det første eksempeltesttilfellet:

  • For $u = 3$, betrakt $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]]$.
  • For $u = 6$, betrakt $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]]$.
  • For $u = 9$, betrakt $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]]$.

Merk at alle $\textit{adj}$ i forklaringen er $1$-indekserte.

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.