Module: Các thành phần được kết nối mạnh mẽ và đồ thị cô đọng


Problem

1 /1


Tìm kiếm các thành phần được kết nối mạnh mẽ

Problem

Bạn được cung cấp một đồ thị có hướng với N đỉnh và M cạnh (1<=N<=20000, 1<=M<=200000). Tìm các thành phần liên thông mạnh của biểu đồ đã cho và sắp xếp theo cấu trúc liên kết thu gọn của nó.
 
Đầu vào
Đồ thị được đưa ra trong tệp đầu vào như sau: dòng đầu tiên chứa các số N và M. M dòng tiếp theo chứa mô tả về cạnh — hai số nguyên từ 1 đến N — số bắt đầu và kết thúc cạnh.
 
Đầu ra
Trên dòng đầu tiên in số K — số lượng các thành phần được kết nối mạnh mẽ trong một biểu đồ nhất định. Trên dòng tiếp theo in N số — đối với mỗi đỉnh, in số thành phần được kết nối mạnh mà đỉnh này thuộc về. Các thành phần liên kết mạnh phải được đánh số sao cho đối với bất kỳ cạnh nào, số lượng thành phần liên kết mạnh ở phần đầu của nó không vượt quá số lượng thành phần liên kết mạnh ở phần cuối của nó.


time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

Nhập Đầu ra
10 19
14
78
5 10
8 9
96
26
6 2
38
9 2
7 2
97
4 5
36
73
6 7
108
10 1
29
27
2
1 2 2 1 1 2 2 2 2 1