Problem
N 個の頂点と M 個のエッジ (1<=N<=20000、1<=M<=200000) を持つ有向グラフが与えられます。与えられたグラフの強結合コンポーネントを見つけ、その凝縮をトポロジカルにソートします。
入力
グラフは入力ファイルで次のように指定されます。最初の行には数値 N と M が含まれます。次の M 行にはそれぞれエッジの説明が含まれます — 1 から N までの 2 つの整数 -エッジの開始番号と終了番号。
出力
最初の行に数字 K を出力します。特定のグラフ内の強連結成分の数。次の行に N 個の数字を表示します —各頂点について、この頂点が属する強連結成分の数を出力します。強連結成分は、どのエッジでも、その始まりの強連結成分の数がその終わりの強連結成分の数を超えないように番号付けする必要があります。
<本体>
|
入る |
出力 |
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
|