Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 難易度: [表示] ハック可能 ✓
統計

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

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.