Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点 M 辺の単純な無向グラフが与えられます。
辺 i は、頂点 A_i と B_i を結んでいます。
頂点 1,2,\ldots,N を順番に消していきます。
なお、頂点 i を消すとは、頂点 i と、頂点 i に接続する全ての辺をグラフから削除することです。
i=1,2,\ldots,N について、頂点 i まで消した時にグラフはいくつの連結成分に分かれていますか?
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )
- 1 \leq A_i \lt B_i \leq N
- i \neq j ならば (A_i,B_i) \neq (A_j,B_j)
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
N 行出力せよ。
i 行目には、頂点 i まで消した時のグラフの連結成分の数を出力せよ。
入力例 1
6 7 1 2 1 4 1 5 2 4 2 3 3 5 3 6
出力例 1
1 2 3 2 1 0
グラフは上図のように変化していきます。
入力例 2
8 7 7 8 3 4 5 6 5 7 5 8 6 7 6 8
出力例 2
3 2 2 1 1 1 1 0
はじめからグラフが非連結なこともあります。
Score : 500 points
Problem Statement
Given is an undirected graph with N vertices and M edges.
Edge i connects Vertices A_i and B_i.
We will erase Vertices 1, 2, \ldots, N one by one.
Here, erasing Vertex i means deleting Vertex i and all edges incident to Vertex i from the graph.
For each i=1, 2, \ldots, N, how many connected components does the graph have when vertices up to Vertex i are deleted?
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )
- 1 \leq A_i \lt B_i \leq N
- (A_i,B_i) \neq (A_j,B_j) if i \neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
Output
Print N lines.
The i-th line should contain the number of connected components in the graph when vertices up to Vertex i are deleted.
Sample Input 1
6 7 1 2 1 4 1 5 2 4 2 3 3 5 3 6
Sample Output 1
1 2 3 2 1 0
The figure above shows the transition of the graph.
Sample Input 2
8 7 7 8 3 4 5 6 5 7 5 8 6 7 6 8
Sample Output 2
3 2 2 1 1 1 1 0
The graph may be disconnected from the beginning.