LCS(HDU_5495 循环节)

传送门：LCS

题意：给出两个序列a_n和b_n，想在给出一个序列p_n，问经过a[p₁],,,,a[p_n]和b[p₁],,,b[p_n]变换后序列a和序列b的最长公共子序列的长度是多少。

思路：对a[i]->b[i]建边，最终总能形成一个环，对于这个长度为L的环，我们总能找到一个长度为L-1的LCS。所以，我们只要用序列的长度减去长度大于1的环的个数就是最终的结果。

例如：

　　　

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
typedef long long ll;
int a[maxn],b[maxn],c[maxn];
int vis[maxn];

inline void init()
{
    memset(vis,0,sizeof(vis));
    return;
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        int n;
        scanf("%d",&n);
        for(int i = 1; i<=n; i++)
            scanf("%d",&a[i]);
        for(int i = 1; i<=n; i++)
        {
            scanf("%d",&b[i]);
            c[a[i]] = b[i];
        }
        int ans = n;
        for(int i = 1; i<=n; i++)
        {
            int t = i;
            if(c[t] != t && !vis[t])
            {
                ans--;
                while(!vis[t])
                {
                    vis[t] = 1;
                    t = c[t];
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
样例输入：
2
3
1 2 3
3 2 1
6
1 5 3 2 6 4
3 6 2 4 5 1
样例输出：
2
4
*/