编程题:并查集
米尔科和斯拉夫科喜欢玩弹珠。在一个激动人心的周五,米尔科想出了一场弹珠比赛,他想展示给斯拉夫科看。在游戏中,米尔科构造了一个方向图,其中所有顶点最多有一条输出边。然后他在其中一个顶点上放置一个弹珠。每当弹珠位于某个顶点$$X$$上时,弹珠都会移动到由单条边连接的相邻顶点(如果存在)。弹珠的移动将继续进行,直到访问了一个没有出射边的顶点,此时弹珠将停止。如果没有这样的顶点被访问,弹珠也有可能无限期地穿过图形。
为了确保斯拉夫科理解比赛规则,米尔科将询问一系列问题。查询类型如下:
$$1.X–$$除非弹珠在循环中卡住,否则如果将其放置在顶点$$X$$上,弹珠会停在哪个顶点上?
$$2.X–$$删除顶点$$X$$的输出边(保证该边始终存在)。
注意:查询是按顺序执行的,并且是累积的(一个影响另一个)。
### 输入格式:
第一行包含一个正整数$$N(1≤N≤300000)$$,表示图中的顶点数。
第二行正好包含由单个空格分隔的$$N$$个正整数,其中位置$$i$$处的数字表示从索引$$i$$的顶点到输出边目的地的索引。零值表示没有从索引$$i$$的顶点到输出边。
下一行包含一个正整数$$Q(1≤Q≤300000)$$,表示查询数量。其余的$$Q$$行包含上述格式的查询。
### 输出格式:
对于类型$$1$$的每个查询,按照执行查询的顺序,输出大理石停止的顶点的索引,每行一个。如果弹珠从未停止,则输出$$CIKLUS$$。
### 输入样例1:
in
3
2 3 1
7
1 1
1 2
2 1
1 2
1 1
2 2
1 2
### 输出样例1:
out
CIKLUS
CIKLUS
1
1
2
### 输入样例2:
in
5
0 3 5 3 4
6
1 1
1 2
2 4
1 2
2 3
1 2
### 输出样例2:
out
1
CIKLUS
4
3
答案:若无答案欢迎评论
为了确保斯拉夫科理解比赛规则,米尔科将询问一系列问题。查询类型如下:
$$1.X–$$除非弹珠在循环中卡住,否则如果将其放置在顶点$$X$$上,弹珠会停在哪个顶点上?
$$2.X–$$删除顶点$$X$$的输出边(保证该边始终存在)。
注意:查询是按顺序执行的,并且是累积的(一个影响另一个)。
### 输入格式:
第一行包含一个正整数$$N(1≤N≤300000)$$,表示图中的顶点数。
第二行正好包含由单个空格分隔的$$N$$个正整数,其中位置$$i$$处的数字表示从索引$$i$$的顶点到输出边目的地的索引。零值表示没有从索引$$i$$的顶点到输出边。
下一行包含一个正整数$$Q(1≤Q≤300000)$$,表示查询数量。其余的$$Q$$行包含上述格式的查询。
### 输出格式:
对于类型$$1$$的每个查询,按照执行查询的顺序,输出大理石停止的顶点的索引,每行一个。如果弹珠从未停止,则输出$$CIKLUS$$。
### 输入样例1:
in
3
2 3 1
7
1 1
1 2
2 1
1 2
1 1
2 2
1 2
### 输出样例1:
out
CIKLUS
CIKLUS
1
1
2
### 输入样例2:
in
5
0 3 5 3 4
6
1 1
1 2
2 4
1 2
2 3
1 2
### 输出样例2:
out
1
CIKLUS
4
3
答案:若无答案欢迎评论