ทบทวน อัลกอริทึม 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$