记录编号	42019	评测结果	AAATAAAAAA
题目名称	[焦作一中2012] 玻璃球游戏	最终得分	90
用户昵称	王者自由	是否通过	未通过
代码语言	C++	运行时间	1.924 s
提交时间	2012-09-10 20:14:02	内存使用	6.01 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 300000 + 10;
int n, q, x[N], y[N];
int b[N], f[N], a[N], s, t;
inline int find(int x) {
    int i = x, j = x, t;
    while(i != f[i]) i = f[i];
    while(j != i) {
        t = f[j];
        f[j] = i;
        j = t;
    } return i;
    //return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {
    freopen("marbles.in", "r", stdin);
    freopen("marbles.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        scanf("%d", b+i);
        f[i] = b[i] ? b[i] : i;
    }
    scanf("%d", &q);
    for(int i=1; i<=q; i++) {
        scanf("%d %d", x+i, y+i);
        if(x[i] == 2) f[y[i]] = y[i];
        else s++;
    } t = s;
    for(int i=q; i>0; i--)
        if(x[i] == 1) a[--t] = find(y[i]);
        else f[y[i]] = (f[b[y[i]]] = find(b[y[i]])) != y[i] ? b[y[i]] : 0;
    for(int i=0; i<s; i++)
        if(a[i]) printf("%d\n", a[i]);
        else printf("CIKLUS\n");
    return 0;
}