問題一覧 > 通常問題

No.2072 Anatomy

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 104
作問者 : chineristACchineristAC / テスター : 37zigen37zigen
4 ProblemId : 8530 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-16 18:47:26

問題文

$N$ 頂点 $M$ 辺の単純連結無向グラフがあります。辺には $1$ から $M$ の番号が付けられており、 $i\ (1\le i \le M)$ 番目の辺は頂点 $u_i,\ v_i$ を結びます。

chinerist 君は以下のような操作をグラフの辺がなくなるまで行い続けました。

操作
  • グラフの各連結成分について、連結成分が辺を持つ場合、辺番号が最小のものを削除する。

chinerist 君は何回操作を行ったか求めてください(操作中に辺を複数本削除しても操作は $1$ 回とカウントします)。

入力

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
  • $2 \leq N \leq 2 \times 10^5$
  • $N-1 \leq M \leq \min(\frac{N(N-1)}{2},\ 2\times 10^5)$
  • $1 \leq u_i < v_i \leq N$
  • 与えられる入力は整数
  • 与えられるグラフは単純連結無向グラフ

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4 3
2 3
1 2
3 4
出力
2

$1$ 回目の操作では頂点 $2,\ 3$ 間の辺が削除され、グラフは頂点 $1,\ 2$ からなる連結成分と頂点 $3,\ 4$ からなる連結成分に分かれます。

$2$ 回目の操作ではそれぞれの連結成分が持つただ $1$ つの辺が削除され、すべての辺が削除されています。

サンプル2
入力
12 20
6 8
1 5
3 5
2 9
2 11
11 12
5 9
7 12
4 11
5 8
7 10
7 11
1 7
7 8
7 9
4 10
6 12
8 11
2 3
1 12
出力
15

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。