题解

问题描述

给定$N$台编号为$0$到$N-1$的网络设备，其中有一组大小为$M$的设备是互斥的——这$M$台设备之间任意两台都不能直接或间接相连。网络工程师收到$X$条连接指令，每条指令是将编号为 $C_j$ 和$D_j$的两台设备连接。如果执行某条指令会导致在互斥设备子集中出现路径相连，则该指令被拒绝并计数，但仍继续处理后续指令。

请在所有指令执行完毕后，输出被拒绝执行的指令总数。

题目内容

有一些网络设备，其中某些设备具备互斥特性，这些设备中任意两台设备都无法直接或间接的连接在一起。 网络工程师按照给定的一系列指令将设备两两连接，可一旦网络工程师判

断连接指令触发了互斥规则，他将拒绝执行这条指令、将其记录并继续执行后续指令。

求所有指令执行完毕后，网络工程师拒绝执行指令的总数。

输入描述

$N\ M\ X$

$A1...Am$

$C1\ D1$

$C2\ D2$

...

$Cx\ Dx$

解释说明:

$Line1:N$:设备总量$(>=1$且$<=1000$,设备会从$0$开始编号)，$M$:互斥设备数量($>=2$且$<=20$)，$x$:指令数量($>=1$且$<=1000$)，固定3个数字，以空格分割。

$Line2$:互斥设备的编号列表，编号数量等于$Line1$的互斥设备数量，不会重复。$Ai$表示互斥设备的编号，$2<=i<=M$

$Line3-LineX+2$:连接指令列表，一共$X$条指令数量，每行代表一条两两设备的连接指令，每行固定两个数字，以空格分割代表需要连接的设备编号,且指令内编号不会重复。$Cj,Dj$分别表示第j条指令中的两个设备，

$1<=j<=N,Cj≠Dj$

输出描述

被拒绝执行的指令条数。

样例1

输入

5 2 5
1 2
0 1 
1 2
2 3
0 3
1 4

输出

2

说明

第$1$条指令，$0$和$1$连接成功，执行成功，未触发互斥规则。此时连接状态为$[0,1]$

第$2$条指令，$1$和$2$不可连接，执行失败，直接触发了互斥规则。此时连接状态依然为$[0,1]$。

第$3$条指令，$2$和$3$连接成功，执行成功,未触发互斥规则。此时连接状态为$[0.1],[2,3]$

第$4$条指令，$0$和$3$不可连接，执行失败，触发了互斥规则。此时连接状杰依然为$[0,1]、[2,3]$。注:若连接成功,则设备$1$和$2$会由于$0$和$3$的连接产生间接连通性。

第$5$条指令，$1$和$4$可连接，执行成功，未触发互斥规则。此时连接状态为$[0,1,4]、[2,3]$。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写