Thứ Tự Topo Của Rút Gọn

Buổi 43 — SCC (Tarjan) & 2-SAT
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho đồ thị có hướng gồm N đỉnh và M cạnh. Hãy xây dựng đồ thị rút gọn (condensation), sau đó in thứ tự topo (topological order) của các SCC. Mỗi SCC được đại diện bởi đỉnh có chỉ số nhỏ nhất trong SCC đó. In các đại diện theo thứ tự topo.

Nếu có nhiều thứ tự topo hợp lệ, in thứ tự có chỉ số đại diện nhỏ nhất trước (lexicographically smallest).

Dữ liệu vào
  • Dòng đầu: hai số nguyên N và M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000)
  • M dòng tiếp theo: u v
Dữ liệu ra
  • Một dòng chứa các đại diện SCC theo thứ tự topo, cách nhau bởi dấu cách.
Ví dụ
Input Output
6 7\n1 2\n2 3\n3 1\n4 5\n5 6\n6 4\n3 4 1 4
Giới hạn
  • 1 ≤ N ≤ 100000
  • 0 ≤ M ≤ 200000
Draft saved