游戏( 并查集(star ))
- 时限:(1s) 内存:(256M)
Descrption
- (Mirko) 和 (Slavko) 爱玩弹球戏。在一个令人激动的星期五,(Mirko) 和 (Slavko) 玩了一把弹球游戏。(Mirko) 构建一个有向图,所有顶点最多有 (1) 条出边。弹球从 (1) 个顶点出发可以沿着一条边移动到它的邻接点,只要它存在,而且它会继续移动到后者的邻接点去,直到最后到达一个找不到出边的顶点才停下来。如果不存在这样的点,弹球可能无限运动下去。
- 为了确信 (Slavko) 理解游戏的规则,(Mirko) 将发起一系列询问,询问的类型如下:
- (1 X) :除非弹球陷入循环,弹球从 (X) 出发,最终将在哪个点停下来。
- (2 X):删除 (X) 的出边(保证该边总是存在)
- 注意:询问是按顺序执行的。
Input
- 第一行包含一个正整数 (N(1<=N<=300000)),表示图的定点数。
- 第二行包含由空格隔开 (N) 个正整数,第 (i) 个数表示从 (i) 顶点可以通过出边到达的定点编号。(0) 表示该点没有出边。
- 接下来的一行包含 (1) 个整数 (Q(1<=Q<=300000)),表示询问的次数。格式如上所示。
Output
- 对于第 (1) 类询问,输出弹球停止时所在顶点编号,每行 (1) 个,按照查询的顺序输出。如果弹球无法停止,则输出 (CIKLUS).
Sample Input
3
2 3 1
7
1 1
1 2
2 1
1 2
1 1
2 2
1 2
Sample Output
CIKLUS
CIKLUS
1
1
2
Hint
- 来源:
分析
- 此题跟大家做过的《打击犯罪》有相似之处,同样是大量的查询与删边,所以,我们应倒序做并查集。
- 所有顶点最多有一条出边,所以我们正好把边的去点当做父亲节点,因为存在删边,我们对原始的父子关系做一个备份,倒序处理的时候再依次把删掉的边还原回来。
- 需要特殊处理的是环的问题,如果是环必然会初选死循环,所以可以加上递归深度维护,具体见代码。
Code
#include <bits/stdc++.h>
const int maxn=3e5+5,maxm=2e4+5;
int f[maxn],ff[maxn];
int a[maxn][2];
int n;
int Find(int x,int Time){
if(Time>n)return f[x]=0;//成环
if(x==f[x])return x;
return f[x]=Find(f[x],Time+1);
}
void Solve(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
f[i]=i;
for(int i=1;i<=n;++i){
int x;scanf("%d",&x);
if(x!=0)f[i]=ff[i]=x;//ff数组为f的备份
}
int Q;scanf("%d",&Q);
for(int i=1;i<=Q;++i){
scanf("%d%d",&a[i][0],&a[i][1]);
if(a[i][0]==2)
f[a[i][1]]=a[i][1];//删边
}
for(int i=Q;i>0;--i){
if(a[i][0]==1)
a[i][1]=Find(a[i][1],0);
else
f[a[i][1]]=ff[a[i][1]];//还原
}
for(int i=1;i<=Q;++i)
if(a[i][0]==1){
if(a[i][1])printf("%d
",a[i][1]);
else printf("CIKLUS
");
}
}
int main(){
Solve();
return 0;
}