問題一覧 > 通常問題

No.1390 Get together

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 236
作問者 : chineristAC / テスター : tatyam
お気に入りにしたユーザー ProblemId : 5132 / 自分の提出
問題文最終更新日: 2021-02-12 18:11:59
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 282 (順位表) の他の問題:

Problem Statement

There are $N$ colored slimes and $M$ boxes. The color of each slime is represented by an integer from $1$ to $N$. Slime $i\ (1\le i\le N)$ is currently in box $b_i$, and its color is $c_i$.

You may perform the following operation any number of times.

  • Choose integers $i,\ j\ (1\le i,\ j\le N)$. Then, move all slimes in box $i$ to box $j$.

By performing this operation $0$ or more times, you want the following to hold: "if slimes $i,\ j$ have the same color, then the boxes containing the $2$ slimes are the same."

Find the minimum number of operations required to achieve this condition.

Input

$N\ M$
$b_1\ c_1$
$b_2\ c_2$
$\vdots$
$b_N\ c_N$
  • $1\le N \le 2\times 10^5$
  • $1\le M \le 2\times 10^5$
  • $1\le b_i \le M\ (1\le i \le N)$
  • $1\le c_i \le N\ (1\le i \le N)$
  • All input values are integers.

Output

Output the answer.

Print a newline at the end.

Sample

Sample 1
Input
5 4
1 1
2 2
3 2
3 3
4 3
Output
2

In the current state, for example, slimes $2,\ 3$ have the same color but are in different boxes, so some operations must be performed.

In fact, the condition can be achieved with the following $2$ operations.

  • Move the slimes in box $2$ to box $3$.
  • Move the slimes in box $3$ to box $4$.
Sample 2
Input
5 5
1 1
2 2
2 3
3 4
3 5
Output
0

The condition is satisfied from the beginning, so no operations are needed.

Sample 3
Input
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
Output
4

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