记录编号	235120	评测结果	WWWWWWWWAW
题目名称	[焦作一中2012] 玻璃球游戏	最终得分	10
用户昵称	水墨青花	是否通过	未通过
代码语言	C++	运行时间	1.537 s
提交时间	2016-03-10 11:03:53	内存使用	6.66 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

struct NODE
{
	int to;
	int father;
	bool del;
	bool incir;
	
	NODE()
	{
		to=0;
		father=0;
		del=false;
		incir=false;
	}
}e[300001];

void Read();
void Work();
void Union(int,int);
int Findroot(int);

int n,q;
int ope[3][300001];
int ans[300001];

int main()
{
	freopen("marbles.in","r",stdin);
	freopen("marbles.out","w",stdout);
	
	memset(ope,0,sizeof(ope));
	memset(ans,0,sizeof(ans));
	
	Read();
	Work();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

void Read()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		e[i].father=i;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&e[i].to);
		if(e[i].to==0)
		{
			e[i].del=true;
		}
	}
	
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d",&ope[1][i]);
		if(ope[1][i]==1)
		{
			scanf("%d",&ope[2][i]);
		}
		else
		{
			scanf("%d",&ope[2][i]);
			e[ope[2][i]].del=true;
		}
	}
}

void Work()
{
	for(int i=1;i<=n;i++)
	{
		if(!e[i].del)
		{
			Union(i,e[i].to);
		}
	}
	for(int i=1;i<=n;i++)
	{
	//	cout<<i<<' '<<e[i].to<<' '<<e[i].father<<endl;
		if(e[i].incir)
		{
			cout<<"aaa";
		}
	}
	
	for(int i=q;i>=1;i--)
	{
		if(ope[1][i]==1)
		{
			if(e[Findroot(ope[2][i])].incir)
			{
				ans[i]=-1;
			}
			else
			{
				ans[i]=Findroot(ope[2][i]);
			}
		}
		else
		{
			Union(ope[2][i],e[ope[2][i]].to);
		}
	}
	
	for(int i=1;i<=q;i++)
	{
		if(ope[1][i]==2)
		{
			continue;
		}
		else
		{	
			if(ans[i]<0)
			{
				printf("CIKLUS\n");
			}
			else
			{
				printf("%d\n",ans[i]);
			}
			
		}
	}
}


void Union(int a,int b)
{
	int rta=Findroot(a);
	int rtb=Findroot(b);
	if(rta==rtb)
	{
		e[rta].incir=true;
		e[rtb].incir=true;
	}
	e[rta].father=rtb;
	
}

int Findroot(int a)
{//cout<<"bbb"<<endl;
	int r=a;
	while(r!=e[a].father)
	{
		r=e[a].father;
	}
	int rt=r;
	r=a;
	while(r!=e[r].father)
	{
		e[r].incir=e[rt].incir;
		e[r].father=rt;
		r=e[r].father;
	}
//	cout<<a<<' '<<e[a].father<<endl;
	return e[a].father;
}