Đồ Thị Rút Gọn

Buổi 43 — SCC (Tarjan) & 2-SAT
Points
25
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. Xây dựng đồ thị rút gọn (condensation graph) bằng cách co mỗi SCC thành một đỉnh. In số đỉnh và số cạnh của đồ thị rút gọn.

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, mỗi dòng chứa hai số nguyên u v (1 ≤ u, v ≤ N)
Dữ liệu ra
  • Một dòng chứa hai số nguyên: số đỉnh và số cạnh của đồ thị rút gọn (mỗi cạnh chỉ đếm một lần dù có nhiều cạnh giữa hai SCC).
Ví dụ
Input Output
6 7\n1 2\n2 3\n3 1\n4 5\n5 6\n6 4\n3 4 2 1
Giới hạn
  • 1 ≤ N ≤ 100000
  • 0 ≤ M ≤ 200000
Draft saved