HDU 5495（dfs）

LCS

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 417    Accepted Submission(s): 216

Problem Description

{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}

Input

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

//因为要形成最大的LCS 所以第二组的排列方式

// 1 4 2 3 5 6

// 3 1 4 2 6 5

//由于下标要相同 所以看成边 就变成求各个回路中的顶点个数

#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=100000+10;
int ans,res;
struct Node  //边太多用邻接表
{
    int v;
    int next;
}edge[maxn];
int pre[maxn],vis[maxn];
void add(int u,int v,int index)
{
    edge[index].v=v;
    edge[index].next=pre[u];
    pre[u]=index;
}
int a[maxn];
int b[maxn];
void dfs(int v)
{
    if(vis[v])return;
    vis[v]=1;
    res++;
    for(int i=pre[v];i!=-1;i=edge[i].next)
    {
        int t=edge[i].v;
        dfs(t);
    }

}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        memset(pre,-1,sizeof(pre));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        int index=1;
        for(int k=1;k<=n;k++)
        {
            scanf("%d",b+k);
            add(a[k],b[k],index);
            index++;
        }
        ans=0;
        for(int i=1;i<=n;i++)
        {
            res=0;
            if(!vis[i])
                dfs(i);
            if(res==1)
                ans+=1;
            else if(res)
                ans+=res-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}