-->
当前位置:首页 > 题库 > 正文内容

编程题:并查集

Luz3年前 (2022-09-05)题库456
米尔科和斯拉夫科喜欢玩弹珠。在一个激动人心的周五,米尔科想出了一场弹珠比赛,他想展示给斯拉夫科看。在游戏中,米尔科构造了一个方向图,其中所有顶点最多有一条输出边。然后他在其中一个顶点上放置一个弹珠。每当弹珠位于某个顶点$$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









答案:若无答案欢迎评论

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。