HDU 5495 LCS (并查集判环)

【题目链接】：click here~~

【题目大意】：

2
3
1 2 3
3 2 1
6
1 5 3 2 6 4
3 6 2 4 5 1

2
4

代码：

/*
* Problem: NO:HDU 5495
* Running time: 764MS
* Complier: G++
* Author: javaherongwei
* Create Time: 15:29 2015/10/4 星期日
*/
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;

#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b

typedef long long LL;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int maxn = 1e5+10;

inline LL read(){
    int  c=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    return c*f;
}
int fa[maxn];
int st[maxn],sb[maxn],sum[maxn];
bool ok;

int Find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=Find(fa[x]);
}

void Merge(int x,int y)
{
    int fx=Find(x);
    int fy=Find(y);
    if(fx==fy) return ;
    else fa[fx]=fy,sum[fy]+=sum[fx];//统计根节点以下元素个数
}

int main()
{
    int t;t=read();
    while(t--)
    {
        int n;
        n=read();
        for(int i=1; i<=n; ++i) st[i]=read();
        for(int i=1; i<=n; ++i) sb[i]=read();
        for(int i=1; i<=n; ++i) sum[i]=1,fa[i]=i;
        for(int i=1; i<=n; ++i)
        {
            Merge(st[i],sb[i]);
        }
        int cnt=0;
        for(int i=1; i<=n; ++i)
        {
            if(fa[i]==i)
            {
                if(sum[i]==1) cnt++;
                else cnt+=sum[i]-1;
            }
        }
        printf("%d\n",cnt);
    }
   return 0;
}

HDU 5495 LCS (并查集判环)

原文：http://blog.csdn.net/u013050857/article/details/48901215