Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Hãy nhớ lại Thuật toán Tarjan dùng để tìm các đỉnh khớp (còn gọi là đỉnh cắt) trong đồ thị vô hướng, có mã giả được trình bày ở Thuật toán 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

Lưu ý rằng trong mã giả, $\textit{adj}[i]$ là mảng chứa tất cả các đỉnh kề với đỉnh $i$, $\textit{parent}$ là mảng mà giá trị khởi tạo của mỗi phần tử là $\text{null}$, và $\textit{visited}$ là mảng mà giá trị khởi tạo của mỗi phần tử là $\text{false}$.

Một số học sinh có thể gặp khó khăn khi tìm hiểu thuật toán này, đặc biệt là từ dòng $19$ đến dòng $22$. Họ không hiểu tại sao Thuật toán Tarjan lại cần tính giá trị $\textit{low}[i]$ theo cách khác nhau, và có thể ghi nhớ nhầm một phiên bản sai của thuật toán. Hãy gọi phiên bản sai này là Thuật toán Trajan, được trình bày ở Thuật toán 2. Chú ý rằng thuật toán Tarjan và Trajan hầu như giống hệt nhau, ngoại trừ tên hàm và $4$ dòng từ dòng $19$ đến dòng $22$.

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh, với mỗi đỉnh $u$ hãy xác định xem có tồn tại đỉnh $v$ và mảng $2$ chiều $\textit{adj}$ ($\textit{adj}$ phải biểu diễn đồ thị đã cho) sao cho $\textsc{Tarjan}(v, 0)$ và $\textsc{Trajan}(v, 0)$ cho kết quả khác nhau tại đỉnh $u$ hay không (tức là Thuật toán Tarjan kết luận đỉnh $u$ là đỉnh khớp trong khi Thuật toán Trajan thì không, hoặc ngược lại).

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^4$) cho biết số lượng bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) cho biết số đỉnh và số cạnh của đồ thị đã cho.

Trong $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i$ và $v_i$ ($1 \le u_i, v_i \le n$) cho biết có một cạnh nối đỉnh $u_i$ và $v_i$ trong đồ thị.

Đảm bảo đồ thị đã cho liên thông và không có khuyên hay cạnh bội. Ngoài ra, cả tổng của $n$ lẫn tổng của $m$ trong tất cả các bộ dữ liệu đều không vượt quá $10^6$.

Kết quả

Với mỗi bộ dữ liệu, in ra một dòng chứa các số nguyên cách nhau bởi một dấu cách theo thứ tự tăng dần. Mỗi số nguyên là một đỉnh mà thuật toán Tarjan và Trajan có thể cho kết quả khác nhau. Nếu không có đỉnh nào như vậy, hãy in ra Empty trên một dòng.

Ví dụ

Dữ liệu vào 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

Kết quả 1

3 6 9
Empty

Giải thích

Đối với bộ dữ liệu ví dụ đầu tiên:

  • Với $u = 3$, xét $v = 1$ và $\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]]$.
  • Với $u = 6$, xét $v = 4$ và $\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]]$.
  • Với $u = 9$, xét $v = 7$ và $\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]]$.

Lưu ý rằng tất cả các mảng $\textit{adj}$ trong phần giải thích đều được đánh số từ $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.