Mạng Lưới Liên Kết

Buổi 43 — SCC (Tarjan) & 2-SAT Buổi 52 — Mock Contest Phase 2
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho đồ thị vô hướng gồm N đỉnh và M cạnh. Sau khi loại bỏ tất cả các cầu (bridge), đồ thị bị chia thành các thành phần liên thông hai-cạnh (2-edge-connected components). Hãy tìm số thành phần liên thông hai-cạnh và cho biết mỗi đỉnh thuộc thành phần nào.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên N 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) mô tả một cạnh vô hướng.

Dữ liệu ra

Dòng đầu tiên in số thành phần liên thông hai-cạnh K.

Dòng thứ hai in N số nguyên, số thứ i là chỉ số thành phần (đánh số từ 1 đến K) mà đỉnh i thuộc vào. Thành phần chứa đỉnh có chỉ số nhỏ nhất được đánh số 1, rồi tiếp tục tương tự.

Ví dụ
Input Output
7 8\n1 2\n2 3\n3 1\n3 4\n4 5\n5 6\n6 7\n7 5 4\n1 1 1 2 3 3 3
Giới hạn
  • 1 ≤ N ≤ 100000
  • 0 ≤ M ≤ 200000
Draft saved