记录编号	42007	评测结果	AAAAAAAAAA
题目名称	[焦作一中2012] 玻璃球游戏	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.878 s
提交时间	2012-09-10 19:39:32	内存使用	8.30 MiB

#include <cstdio>
#include <cstdlib>
using namespace std;
const int MAXN=300100;
int N,P,Edge[MAXN],Num[MAXN],Ans[MAXN];
int Opera[MAXN],Operb[MAXN],Stop[MAXN],Del[MAXN];
    
//int find(int k) {return (Num[k]==k?k:(Num[k]=find(Num[k])));}
inline void Merge(int x,int y){Num[x]=y;}
    
inline int find(int k)
{
    int i=k; while(i!=Num[i]) i=Num[i];
    int j=k,tmp; while(j!=i)
    {
        tmp=Num[j];
        Num[j]=i;
        j=tmp;
    }return i;
}
    
inline void init()
{
    int x,y;
    for(int i=1;i<=P;i++)
        if(Opera[i]==2) Del[i]=Edge[Operb[i]],Edge[Operb[i]]=0;
    for(int i=1;i<=N;i++) Num[i]=i,Stop[i]=i;
    for(int i=1;i<=N;i++)
    {
        if(Edge[i]==0) continue;
        x=find(i),y=find(Edge[i]);
        if(x==y) Stop[x]=-1;
        else Merge(x,y);
    }
}
    
inline void solve()
{
    int x,y;
    for(int i=P;i>=1;i--)
    {
        if(Opera[i]==1) {Ans[i]=Stop[find(Operb[i])];continue;}
        x=find(Operb[i]),y=find(Del[i]);
        if(x==y) Stop[x]=-1;
        else Merge(x,y); Ans[i]=0;
    }
    for(int i=1;i<=P;i++)
        if(Ans[i]==-1) printf("CIKLUS\n");
        else if(Ans[i]!=0) printf("%d\n",Ans[i]);
}
    
int main()
{
    freopen("marbles.in","r",stdin);
    freopen("marbles.out","w",stdout);
    scanf("%d\n",&N);
    for(int i=1;i<=N;i++) scanf("%d",&Edge[i]);scanf("%d\n",&P);
    for(int i=1;i<=P;i++) scanf("%d %d\n",&Opera[i],&Operb[i]);
    init(); solve();
    return 0;
}