問題一覧 > 通常問題

No.1390 Get together

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 226
作問者 : chineristAC / テスター : tatyam
13 ProblemId : 5132 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-12 18:11:59

問題文

N 匹の色付きスライムと M 個の箱があります。各スライムの色は 1 から N の整数であらわされます。スライム i (1≤i≤N) は現在箱 bi の中におり、色は ci です。

あなたは以下の操作を好きな回数だけ行うことができます。

  • 整数 i, j (1≤i, j≤N) を選ぶ。そのあと箱 i の中にいるすべてのスライムを箱 j に移す。

この操作を 0 回以上行うことで「スライム i, j の色が同じならば、 2 匹のスライムがいる箱は同じである」が成り立つようにしたいです。

この条件を達成するのに必要な最小の操作回数を求めてください。

入力

N M
b1 c1
b2 c2
⋮
bN cN
  • 1≤N≤2×105
  • 1≤M≤2×105
  • 1≤bi≤M (1≤i≤N)
  • 1≤ci≤N (1≤i≤N)
  • 与えられる入力はすべて整数

出力

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

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

サンプル

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

現在の状態ではたとえばスライム 2, 3 は同じ色を持ちますがそれぞれ異なる箱に入れられているので何かしら操作を行わなくてはなりません。

実際には以下の 2 回の操作で条件を達成できます。

  • 箱 2 のスライムを箱 3 に移す
  • 箱 3 のスライムを箱 4 に移す
サンプル2
入力
5 5
1 1
2 2
2 3
3 4
3 5
出力
0

はじめから条件を満たしているので操作を行う必要がありません。

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

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