记录编号	590981	评测结果	AAAAAAAAAA
题目名称	[焦作一中2012] 玻璃球游戏	最终得分	100
用户昵称	liuyiche	是否通过	通过
代码语言	C++	运行时间	0.787 s
提交时间	2024-07-14 23:34:33	内存使用	8.42 MiB

#include <bits/stdc++.h>

using namespace std;

int n, q;
int fa[300010];
bool vis[300010];
int d[300010];
bool pd[300010];
int ans[300010];

struct qus
{
    int op;
    int x;
};
qus v[300010];

inline int get(int step)
{
	if(fa[step] == -1)
        return -1;
    if(vis[step] == 1)
        return fa[step] = -1;
    if (fa[step] == step)
		return step;
    vis[step] = 1;
	fa[step] = get(fa[step]);
	vis[step] = 0;
	return fa[step];
}

inline void merge(int x, int y)
{
	int xroot = get(x);
	vis[x] = 1;
    fa[xroot] = get(y);
    vis[x] = 0;
}

int main()
{
    freopen("marbles.in", "r", stdin);
    freopen("marbles.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i)
        fa[i] = i;
    for(int i = 1; i <= n; ++i)
        cin >> d[i];
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        cin >> v[i].op >> v[i].x;
        if(v[i].op == 2) pd[v[i].x] = 1;
    }
    for(int i = 1; i <= n; ++i)
        if(d[i] != 0 && pd[i] == 0)
            merge(i,d[i]);
    for(int i = q; i > 0; --i)
    {
        if(v[i].op == 1)
            ans[i] = get(v[i].x);
        else
            if(d[v[i].x] != 0)
                merge(v[i].x,d[v[i].x]);
    }
    for(int i = 1; i <= q; ++i)
        if(v[i].op == 1)
        {
            if(ans[i] == -1)
                cout << "CIKLUS" << '\n';
            else cout << ans[i] << '\n';
        }

   	return 0;
}