题目描述

有 n 个气球（编号 1∼n），其中第 i 个气球的颜色为 ci。

气球一共有 k 种颜色（编号 1∼k），每个气球的颜色 ci 都满足 1≤ci≤k。

接下来要进行 m 次询问，每次询问给定两个整数 l,r，并询问第 l 个气球和第 r 个气球的颜色是否相同。

我们希望所有询问都能得到肯定的回答（即每次询问的两个气球的颜色都相同）。

为了达成这一目的，我们可以对其中一些气球进行重新染色，被重新染色的气球的颜色也应在 [1,k] 范围内。

为了节约染料，我们希望重新染色的气球数量尽可能少。

请问，最少需要重新染色多少个气球。

注意，所有染色必须在第一次询问开始之前完成。

样例

输入
3 2 3
1 2 3
1 2
2 3
输出
2

并查集

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int p[N], sz[N];
int a[N];
int n, m, k;
vector<int> s[N];
int find(int x) 
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i ++ )p[i] = i, sz[i] = 1;
    for (int i = 1; i <= n; i ++ )cin>>a[i];
    while(m -- ){
        int a, b;
        cin>>a>>b;
        int fa = find(a), fb = find(b);
        if(fa != fb){
            p[fa] = fb;
            sz[fb] += sz[fa];
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++ ){
        int fa = find(i);
        s[fa].push_back(a[i]);
    }
    for(int i = 1; i <= n; i ++ ){
        sort(s[i].begin(), s[i].end());
    }
    for(int i = 1; i <= n; i ++ ){
        if(s[i].size() == 1 || s[i].size() == 0) continue;
        int last = -1, mx = 0, cnt = 0;
        for(auto x : s[i]){
            if(x != last){
                mx = max(mx, cnt);
                cnt = 1;
                last = x;
            }
            else cnt ++;
        }
        if(cnt) mx = max(mx, cnt);
        ans += s[i].size()-mx;
    }
    cout<<ans;
}