记录编号	235017	评测结果	AAAAAAAAAA
题目名称	[焦作一中2012] 玻璃球游戏	最终得分	100
用户昵称	森林	是否通过	通过
代码语言	C++	运行时间	1.061 s
提交时间	2016-03-10 09:38:18	内存使用	4.37 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=300010;
int father[maxn],n,Q[maxn]={0},A[maxn]={0},to[maxn]={0};
bool ope[maxn]={0},circle[maxn]={0};
int Find(int x){
	int rt=x,tot=0;
	while(rt!=father[rt]){
		tot++;
		rt=father[rt];
		if(tot>n)return -1;
	}
	int tmpt;
	while(x!=father[x]){
		tmpt=father[x];
		father[x]=rt;
		x=tmpt;
	}
	return rt;
}
void unione(int a,int b){
	int aa=Find(a),ab=Find(b);
	if(aa==ab){
		circle[aa]=1;circle[ab]=1;
	}
	father[aa]=ab;
}
int QR(){
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	int x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return x;
}
int main(){
	freopen("marbles.in","r",stdin);
	freopen("marbles.out","w",stdout);
	n=QR();
	for(int i=1;i<=n;i++)father[i]=i;
	for(int i=1;i<=n;i++)
		to[i]=QR();
	int q,type,x;q=QR();
	for(int i=1;i<=q;i++){
		type=QR();x=QR();
		if(type==1)Q[i]=x;
		else {
			Q[i]=-x;
			ope[x]=1;
		}
	}
	for(int i=1;i<=n;i++)
		if(!ope[i]&&to[i]!=0){
			unione(i,to[i]);
		}
	for(int i=q;i>=1;i--){
		if(Q[i]>0){
			int k=Find(Q[i]);
			if(circle[k])A[i]=-1;
			else
			A[i]=k;
		}
		else {
			int t=-Q[i];
			unione(t,to[t]);
		}
	}
	for(int i=1;i<=q;i++){
		if(Q[i]>0){
			if(A[i]==-1)printf("CIKLUS\n");
			else printf("%d\n",A[i]);
		}
	}
	return 0;
}