0724 - 網 (net)

問題

網があります。

ナウ人間君は、「網って何個閉路があるんだろう！ｗ」って思いました。

この網は特殊で、網の交点となるところからほかの交点へと無造作に複数つながれているし、
しかもこの網は交点だけがぽつんと置いてあったり、途中で切れていることがある始末。もはや網ではない。

「なんだこの網！　ナンダストラ！　網って・・・こういうものなのかな・・・・」　

いやだねぇ

課題　

網の交点の数、交点と交点をつなぐ線の数、その線の具体的な情報が与えられるので、
その網に閉路が何個存在するのかを求め、個数を出力せよ。

閉路の判定

線をつないだ結果、すべての頂点が網の交点である多角形ができた場合、それを一つの閉路とする。

中に閉路を二つ以上含むような多角形は、閉路として考えないこととする。

頂点の結ばれ方が全く同じである閉路は2つ以上あってはならないものとする。

入出力例の図を参照すると分かりやすいかもしれない。

入力

1行目に網の交点の数 n , 交点と交点をつなぐ線の数 m が与えられる。

2行目 ~ 1 + m 行目まで、交点と交点をつなぐ線 a_i , b_i が与えられる。

n m
a1 b1
a2 b2
a3 b3
  .
  .
  . 
am bm

出力

網に含まれる閉路の数を一行に出力せよ。

制約

• 2 ≦ n ≦ 100000
• 1 ≦ m ≦ 200000
• 1 ≦ a_i < b_i ≦ n
• 多重辺, 自己ループは存在しない。
  つまり、i ≠ j において ( a_i = a_j かつ b_i = b_j ) は存在しない。

すべての網の交点が線で連結されているとは限らないことに注意せよ。

入出力例

入力例1

6 8
1 2
2 3
1 3
2 4
3 4
3 5
4 6
5 6

出力例1

3

解説

この図のように三つ閉路ができているため、答えは3となる。

入力例2

12 16
1 2
1 3
3 4
2 4
4 5
4 8
4 7
5 6
7 8
6 7
7 9
8 9
9 10
10 11
11 12
9 12

出力例2

5

コメント

深さの問題作ってたら、幅の問題でもあった。

さらにユニ木を使ってでも解ける問題であることが分かった。いろんな解法で解くの、おすすめだヨ☆＞＜：D:DXD iXgy