Search for strongly connected components
Problem
You are given a directed graph with N vertices and M edges (1<=N<=20000, 1<=M<=200000). Find the strongly connected components of the given graph and topologically sort its condensation.
Input
The graph is given in the input file as follows: the first line contains the numbers N and M. Each of the next M lines contains a description of the edge — two integers from 1 to N — edge start and end numbers.
Output
On the first line print the number K — the number of strongly connected components in a given graph. On the next line print N numbers — for each vertex print the number of the strongly connected component that this vertex belongs to. The strongly connected components must be numbered in such a way that for any edge the number of the strongly connected component of its beginning does not exceed the number of the strongly connected component of its end.
|
Enter |
Output |
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
|
2
1 2 2 1 1 2 2 2 2 1
|