526互联

tarjan、缩点、删点、删边

发布时间 2023-10-26 17:42:24作者: 青阳buleeyes

D. Cyclic Operations

好久没有用 tarjan 了，今天做一道题，顺便复习一下

tarjan 是用来求连通性的算法，时间复杂度 O(n)。网上关于 tarjan 的博文很多，我这里就不写了，只是复习一下。

这道题很容易想到建边 i-a[i]：

对于长度是 k 的环，很显然可以满足；

对于长度不是 k 的环，无论如何都不能满足；

对于不构成环的点，可以随意向环中的点借位，因为不构成环，所以彼此互不影响，被借位的环中的点最后覆盖即可。

上代码：

#include<bits/stdc++.h>
#define inf 1000000000
#define mod 998244353
using namespace std;
const int N=1e6+10;
int n,m,t,k,qq,tot,deep,sum,top;
int f[N],dp[N],a[N],h[N],H[N],num[N];
int dfn[N],low[N],vis[N],Stack[N],color[N],cnt[N];
vector<int>e[N];
void tarjan(int u){
    dfn[u]=low[u]=++deep;
    vis[u]=1;
    Stack[++top]=u;
    for(int v:e[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        color[u]=++sum;
        vis[u]=0;num[sum]++;
        while(Stack[top]!=u){
            num[sum]++;
            color[Stack[top]]=sum;
            vis[Stack[top--]]=0;
        }
        --top;
    }
}
void init(){

}
void solve(){
    cin>>n>>k;
    for(int i=1;i<=2*n;++i) dfn[i]=vis[i]=color[i]=num[i]=low[i]=Stack[i]=0;
    for(int i=1;i<=n*2;++i) e[i].clear();
    deep=top=0;
    for(int i=1;i<=n;++i) cin>>a[i],e[i].push_back(a[i]);
    if(k==1){
        for(int i=1;i<=n;++i){
            if(a[i]!=i){ cout<<"NO"<<endl;return; }
        }
        cout<<"YES"<<endl;
    }
    else{
        for(int i=1;i<=n;++i){
            if(a[i]==i){ cout<<"NO"<<endl;return; }
        }
        for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
        for(int i=1;i<=n;++i){
            if(num[color[i]]!=k&&num[color[i]]!=1){
                cout<<"NO"<<endl;return;
            }
        }
        cout<<"YES"<<endl;
    }
}
signed main(){
    int T=1;
    cin>>T;
    init();
    while(T--) solve();
    return 0;
}