Teemo's bad day (并查集)

2018-08-02

Teemo’s bad day

题意

给两个相同长度的数组A，B，一次操作是改变A，B中相同的数字x为->y。如果A[i]=B[i]，i<=n，都成立，则完成。问最少的操作次数。

裸并查集。find(a[i])!=find(b[i]),cnt++。

看！代码

#include <bits/stdc++.h>
using namespace std;
int a[500010],b[500010];
int fa[100010];
int Find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=Find(fa[x]);
}
void Union(int p,int q)
{
    int rp=Find(p),rq=Find(q);
    if(rp!=rq)
        fa[rp]=rq;
}
void init(int n)
{
    for(int i=0;i<100010;i++)
        fa[i]=i;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,cnt=0;
        scanf("%d",&n);
        init(n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&b[i]);
            if(a[i]==b[i]) continue;
            if(Find(a[i])!=Find(b[i]))
            {
                cnt++;Union(a[i],b[i]);
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}