给定一个数组$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; }