记录编号	589910	评测结果	AAAAAAAAAA
题目名称	[焦作一中2012] 玻璃球游戏	最终得分	100
用户昵称	彭欣越	是否通过	通过
代码语言	C++	运行时间	3.550 s
提交时间	2024-07-08 17:00:19	内存使用	7.56 MiB

#include <bits/stdc++.h>
using namespace std;
int n,q,a[300010],b[300010],f[300010],cnt,t[300010];
struct node {
    int a,b;
}c[300010];
int find (int x) {
    if (f[x]==x) return x;
    return f[x]=find(f[x]); 
}
int main () {
    freopen("marbles.in","r",stdin);
    freopen("marbles.out","w",stdout);
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        b[i]=a[i];
    }
    for (int i=1;i<=n;i++) f[i]=i;
    cin >> q;
    for (int i=1;i<=q;i++) {
        cin >> c[i].a >> c[i].b;
        if (c[i].a==2) b[c[i].b]=0; 
    }
    for (int i=1;i<=n;i++) {
        if (b[i]==0) continue;
        if (find(i)==find(b[i])) {
            f[find(b[i])]=0;
        }
        f[find(i)]=find(b[i]);
    }
    while (q) {
        //cout << q <<endl;
        int fx=find(c[q].b),fy=find(a[c[q].b]);
        //cout << fx <<' '<< c[q].b <<endl;
        if (c[q].a==1) {
            if (fx==0) t[++cnt]=-1;
            else t[++cnt]=fx;
        }else{
            if (fx==fy) {
                //cout << fx <<' '<< fy <<' '<< find(2) <<endl;
                f[fy]=0;
            }
            f[fx]=f[fy];
            //cout << f[fx] <<' '<< f[fy] <<endl; 
            //cout << find(fx) <<endl;
        }
        q--;
    }
    for (int i=cnt;i>=1;i--) {
        if (t[i]==-1) cout << "CIKLUS" <<endl;
        else cout << t[i] <<endl;
    }
    return 0;
}