P6706 [COCI 2010/2011 #7] KUGLICE

洛谷

由于每一个节点最多只会连出一条边，所以一个连通的图必定是基环树或者树。

如果是基环树，那么一定会有环，且经过移动后必定在环内，直接按照有环的情况输出即可。

对于一颗树，我们可以将这一个节点连向的点视为父亲，那么最后的答案就是这棵树的根。

我们可以通过并查集来模拟建树的过程，但是拆树的过程并不好模拟，怎么办？

我们可以考虑离线操作，要拆掉的边先不连接，反过来处理就成为了建边的过程。

剩下的就是对并查集建树以及判断是否有环的简单运用了，这里就不过多说明了，可以自己看代码。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[300005],b[300005],fa[300005];
int find(int x){if(x==fa[x])return x;return fa[x]=find(fa[x]);
}
bool merge(int x,int y){y=find(y);if(y==x)return false;fa[x]=y;return true;
}
bool f[300005];
struct Q{int op,x,res;
}q[300005];
signed main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)b[i]=a[i];cin>>m;for(int i=1;i<=m;i++)cin>>q[i].op>>q[i].x;for(int i=1;i<=m;i++){if(q[i].op==2){b[q[i].x]=0;}}for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=n;i++){if(!b[i])continue;if(!merge(i,b[i]))f[i]=1;}for(int i=m;i>=1;i--){if(q[i].op==1){int tmp=find(q[i].x);if(f[tmp])q[i].res=-1;else q[i].res=tmp;}else {if(!merge(q[i].x,a[q[i].x]))f[q[i].x]=1;}}for(int i=1;i<=m;i++){if(q[i].op==1){if(q[i].res==-1)puts("CIKLUS");else cout<<q[i].res<<endl;}}return 0;
}