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

ทบทวน อัลกอริทึม Tarjan สำหรับคำนวณหาจุดเชื่อมต่อสำคัญ (articulation points หรือ cut vertices) ในกราฟไม่มีทิศทาง ซึ่งมีรหัสเทียมแสดงอยู่ในอัลกอริทึมที่ 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$ พวกเขาไม่เข้าใจว่าทำไม อัลกอริทึม Tarjan จึงต้องคำนวณค่าของ $\textit{low}[i]$ แตกต่างกัน และอาจจำอัลกอริทึมรุ่นที่ผิดไว้ในใจ เรียกอัลกอริทึมรุ่นที่ผิดนี้ว่า อัลกอริทึม Trajan ซึ่งแสดงอยู่ในอัลกอริทึมที่ 2 สังเกตว่าอัลกอริทึม Tarjan และ Trajan แทบจะเหมือนกันทุกประการ ยกเว้นชื่อฟังก์ชันและ $4$ บรรทัดตั้งแต่บรรทัดที่ $19$ ถึงบรรทัดที่ $22$

กำหนดกราฟไม่มีทิศทางที่เชื่อมต่อกันซึ่งมี $n$ จุดยอดและ $m$ เส้นเชื่อม สำหรับแต่ละจุดยอด $u$ จงพิจารณาว่ามีจุดยอด $v$ และอาเรย์ $2$ มิติ $\textit{adj}$ ($\textit{adj}$ ต้องแทนกราฟที่กำหนด) ที่ทำให้ $\textsc{Tarjan}(v, 0)$ และ $\textsc{Trajan}(v, 0)$ ให้ผลลัพธ์แตกต่างกันที่จุดยอด $u$ หรือไม่ (กล่าวคือ อัลกอริทึม Tarjan ระบุว่าจุดยอด $u$ เป็นจุดเชื่อมต่อสำคัญในขณะที่ อัลกอริทึม Trajan ไม่ได้ระบุเช่นนั้น หรือในทางกลับกัน)

ข้อมูลนำเข้า

มีหลายกรณีทดสอบ บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็ม $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$ ($1 \le u_i, v_i \le n$) แทนว่ามีเส้นเชื่อมที่เชื่อมจุดยอด $u_i$ และ $v_i$ ในกราฟ

รับประกันว่ากราฟที่กำหนดเชื่อมต่อกัน และไม่มีวงวนในตัวเองหรือเส้นเชื่อมซ้ำ นอกจากนี้ ทั้งผลรวมของ $n$ และผลรวมของ $m$ ของทุกกรณีทดสอบจะไม่เกิน $10^6$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้แสดงผลหนึ่งบรรทัดที่มีจำนวนเต็มบางจำนวนคั่นด้วยช่องว่างหนึ่งช่องเรียงตามลำดับจากน้อยไปมาก แต่ละจำนวนเต็มคือจุดยอดที่อัลกอริทึม Tarjan และ Trajan อาจให้ผลลัพธ์แตกต่างกัน หากไม่มีจุดยอดดังกล่าว ให้แสดงผล 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$

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.