HDU 5495 LCS (並查集判環)

HDU 5495 LCS (並查集判環)

 

【題目大意】：

 

Problem Description You are given two sequence {a1,a2,...,an} and {b1,b2,...,bn}. Both sequences are permutation of {1,2,...,n}. You are going to find another permutation {p1,p2,...,pn} such that the length of LCS (longest common subsequence) of {ap1,ap2,...,apn} and {bp1,bp2,...,bpn} is maximum.
Input There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n(1≤n≤105) - the length of the permutation. The second line contains n integers a1,a2,...,an. The third line contains nintegers b1,b2,...,bn.

The sum of n in the test cases will not exceed 2×106.
Output For each test case, output the maximum length of LCS.
Sample Input

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

Sample Output

2
4

【思路】：題目中給出的是兩個排列, 於是我們我們可以先把排列分成若干個環, 顯然環與環之間是獨立的. 事實上對於一個長度為l (l > 1)l(l>1)的環, 我們總可以得到一個長度為l-1l−1的LCS, 於是這個題的答案就很明顯了, 就是nn減去長度大於11的環的數目.

 

代碼：

 

/*
* Problem: NO:HDU 5495
* Running time: 764MS
* Complier: G++
* Author: javaherongwei
* Create Time: 15:29 2015/10/4 星期日
*/
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define min(a,b) ab?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
,cnt);
    }
   return 0;
}