CF1867D Cyclic Operations
One_JuRuo
·
·
题解
前言
赛时没调出来，赛后调了一个上午，最后发现是有个地方没清零。
思路
首先对于位置 i，我们必须要保证进行的操作中，最后一次出现 i，i 的后面一定是 a_i。
那么我们考虑统计所有位置上的要求，用有向边链接，那么就会出现一个有环有向图（一定有环，因为点数等于边数）。
那么，自然想到缩点。
首先，如果有某个环的长度不为 k（不讨论长度为 1 的情况），那么一定无解，因为总会剩几个点没办法改，或者为了改最后几个点而导致把最开始的点改了，自己手玩一下应该很好理解。
那么还有不构成环的，也可以理解成长度为 1 的情况，我们可以先满足这些边的要求，这样可能会使得环内得答案不正确，但是我们可以最后再处理环，把之前错误的答案改正确。
所以做法就出来了，先建图，然后 tarjan 缩点，统计每个环的长度，长度要么为 k，要么为 1，如果存在不是 k 也不是 1 肯定无解，然后再统计长度为 k 的个数，如果没有也肯定无解，否则就是有解。
另外，还有 k=1 的特殊情况，这种情况，必须满足 a_i=i，也就是它只能每次选一个值 l，那必定是把 a_l 改成 l，所以必须满足上述条件。
## AC code
```cpp
#include<bits/stdc++.h>
using namespace std;
int T,n,k,a[100005],e[100005],ne[100005],h[100005],num,idx=1,dcnt,siz[100005],dfn[100005],low[100005],z[100005],top,in_z[100005],ff,flag;
inline void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u)
{
dfn[u]=low[u]=++dcnt,in_z[u]=1,z[++top]=u;
for(int i=h[u];i;i=ne[i])
{
if(!dfn[e[i]]) dfs(e[i]),low[u]=min(low[u],low[e[i]]);
else if(in_z[e[i]]) low[u]=min(low[u],dfn[e[i]]);
}
if(dfn[u]==low[u])
{
++num;
while(z[top+1]!=u) in_z[z[top--]]=0,++siz[num];//因为这个写法，可能和上一次的进栈的元素相同，导致错误，所以要初始化z数组。
}
}
inline bool sol()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n+1;++i) z[i]=siz[i]=h[i]=dfn[i]=0;//因为判断是z[top+1]，所以要多预处理一位
//奇怪的是，我在洛谷这么写都没错，难道是洛谷没卡这种情况？
idx=1,num=flag=dcnt=top=0;
if(k==1)
{
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) if(i!=a[i]) return 0;
return 1;
}
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) if(i==a[i]) return 0;else add(i,a[i]);
for(int i=1;i<=n;++i) if(!dfn[i]) dfs(i);
for(int i=1;i<=num;++i)
{
if(siz[i]!=1&&siz[i]!=k) return 0;
if(siz[i]==k) flag=1;
}
return flag;
}
int main()
{
scanf("%d",&T);
while(T--)
if(sol()) puts("YES");
else puts("NO");
return 0;
}
```