题解：CF1327D Infinite Path

· · 题解

这类有类似置换操作的题，第一反应应该是直接建图。后面默认是从 p_i 到 i 连边建图。

现在我以样例2为例举个例子。

下图分别是是 p^1，p^2，p^3 中的一个环。

发现规律了吗？对于图 p^k 的某个环来说，其每条边都相当于是图 p^1 向前走了 k 步。设此环在 p^1 中的长为 m，m 和 k 最大公约数为 d，则环上模 d 同余的点在 p^k 上一定在同一个环上。

那么思路就非常简单了。先找环，然后枚举最大公约数 d， 找出这个环上所有新环是否颜色相同，更新答案。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,p[N],c[N];
bool v[N];
int cnt;
vector<int>circle[N];
int ans,m,a[N];
void dfs(int x){//找环
    if(v[x])return ;
    v[x]=1;
    circle[cnt].push_back(c[x]);
    dfs(p[x]);//因为其实(i,pi)连边建图和(pi,i)连边建图等价，所以这么写较为简便
}
int num[N];
void work(){
    for(int d=1;d<=m;d++){
        if(m%d!=0)continue;
        for(int i=0;i<d;i++)num[i]=0;
        for(int i=1;i<=m;i++){
            int x=i%d;
            if(num[x]==0)num[x]=a[i];
            else if(num[x]!=a[i])num[x]=-1;
        }
        bool p=0;
        for(int i=0;i<d;i++){
            if(num[i]!=-1){p=1;break;}
        }
        if(p){
            ans=min(ans,d);
            return ;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int T;cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>p[i];
        for(int i=1;i<=n;i++)cin>>c[i];
        ans=1145141919810ll;
        for(int i=1;i<=n;i++)v[i]=0;
        cnt=0;
        for(int i=1;i<=n;i++){
            if(!v[i]){
                cnt++;circle[cnt].clear();
                dfs(i);
            }
        }
        for(int i=1;i<=cnt;i++){
            m=circle[i].size();
            ans=min(ans,m);
            for(int j=1;j<=m;j++)a[j]=circle[i][j-1];
            work();
        }
        cout<<ans<<"\n";
    }
    return 0;
}