No.1390 Get together
タグ : / 解いたユーザー数 236
作問者 :
tatyam
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もしくは右上の雲マークをクリックしてアカウントを作成してください。