记录编号	256974	评测结果	AAAAAAAAAA
题目名称	[焦作一中2012] 玻璃球游戏	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.814 s
提交时间	2016-05-01 21:28:24	内存使用	5.49 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define isconnected(x,y) (findroot(x)==findroot(y))
using namespace std;
namespace mine{
	int __c,__x,__a[110],__i,__j;
	bool __neg;
	inline int getint(){
		__x=__neg=0;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=(__x<<1)+(__x<<3)+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline void putint(int __x){
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j>=0;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
const int maxn=300010;
struct cmd{
	int type,num;
}a[maxn];
int findroot(int);
void merge(int,int);
int prt[maxn],to[maxn];
bool del[maxn];
char result[maxn][10];
int n,m;
int v[maxn],k=-1;
int i,type,num,rt;
int MAIN(){
#define COGS
#ifdef COGS
	freopen("marbles.in","r",stdin);
	freopen("marbles.out","w",stdout);
#endif
	n=getint();
	for(i=1;i<=n;i++){
		to[i]=getint();
		prt[i]=i;
	}
	memset(del,0,sizeof(bool)*(n+5));
	m=getint();
	for(i=m-1;i>-1;i--){
		scanf("%d%d",&a[i].type,&a[i].num);
		if(a[i].type==2)del[a[i].num]=true;
	}
	for(i=1;i<=n;i++)if(!del[i]&&to[i])merge(i,to[i]);
	for(i=0;i<m;i++){
		type=a[i].type;
		num=a[i].num;
		if(type==1){
			rt=findroot(num);
			if(rt==-1)sprintf(result[i],"CIKLUS\n");
			else sprintf(result[i],"%d\n",rt);
		}
		else if(type==2&&del[num])merge(num,to[num]);
	}
	for(i=m-1;i>-1;i--)printf(result[i]);
	return 0;
}
int haha=MAIN();
inline int findroot(int x){
	k=-1;
	while(prt[x]!=x&&prt[x]!=-1){
		v[++k]=x;
		x=prt[x];
	}
	for(int i=0;i<k;i++)prt[v[i]]=v[k];
	return prt[x];
}
int rx,ry;
inline void merge(int x,int y){
	rx=findroot(x);
	ry=findroot(y);
	if(rx==ry)prt[rx]=-1;
	else prt[rx]=ry;
}
int main(){;}