Two-Edge-Connected Components

AC一覧

Problem Statement (Japanese) / 問題文 (日本語)

$N$ 頂点 $M$ 辺の無向グラフが与えられる。$i$ 番目の辺は $(a_i, b_i)$ である。このグラフは単純とは限らない。 このグラフを二辺連結成分分解してください。

Constraints / 制約

Input / 入力

$N$ $M$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{M - 1}$ $b_{M - 1}$

Output / 出力

$K$ を二辺連結成分の個数として、$1 + K$ 行出力する。 最初の行には $K$ を出力し、その後 $K$ 行では以下のように出力する。$l$ は二辺連結成分の頂点数であり、$v_i$ はその頂点番号である。

$l$ $v_0$ $v_1$ ... $v_{l-1}$

正しい出力が複数存在する場合は、どれを出力しても構わない。

Sample / サンプル

# 1

4 5
0 2
0 1
3 0
2 1
2 3
1
4 0 2 1 3

# 2

13 21
4 5
8 7
12 3
3 10
1 5
10 2
0 0
11 4
2 12
9 1
9 0
7 8
7 6
9 1
8 2
12 10
11 0
8 6
3 2
5 9
4 11
3
6 0 9 1 5 4 11
4 2 10 3 12
3 6 7 8

# 3

2 2
0 1
1 0
1
2 0 1

Forum


Timelimit: 5 secs