codeforces图论合集

Cyclic Operations

给定一个数组$a$，每次构造一个数组$\space l \space$长度为$\space k\space$，数组$\space a\space$与$\space l\space$转换关系如下 :

$a_{l_1}\to l_2\space,\space a_{l_2}\to l_3\space,\space a_{l_3}\to l_4\space,\space...\space,\space a_{l_n}\to l_1$

这种数组值与位置相关的题目，感觉有种常见的 trick 就是对于值和位置连边判环，这题判断环是不是都是k元环即可

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N=1e5+5;
//bel数组记录某个点在哪个连通块里面
vector<int>edge[N];
int dfn[N],low[N],ins[N],bel[N],idx,n,m,cnt;
stack<int>stk;
vector<vector<int>>scc;

void dfs(int u){
    dfn[u]=low[u]=++idx;
    ins[u]=true; stk.push(u);
    for(auto v:edge[u]){
        if(!dfn[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }else{
            if(ins[v])low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        vector<int>c;
        cnt++;
        while(1){
            int v=stk.top(); bel[v]=cnt;
            stk.pop(); ins[v]=false;
            c.push_back(v);
            if(v==u)break;
        }
        scc.push_back(c);
    }
}

void init() {
    for(int i = 0; i <= n; i++) {
        dfn[i] = low[i] = 0;
        edge[i].clear();
        if(i < cnt) scc.clear();
    }
    idx = cnt = 0;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1; cin >> T;
    while(T--) {
        int k; cin >> n >> k;
        init();
        bool ok = true;
        for(int i = 1; i <= n; i++) {
            int x; cin >> x;
            edge[i].push_back(x);
            if(i == x && k != 1) ok = false;
            if(k == 1 && x != i) ok = false; 
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i]) dfs(i);
        }
        for(int i = 0; i < cnt; i++) {
            if((int)scc[i].size() != 1 && (int)scc[i].size() != k) ok = false;
        }
        if(ok) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}