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