题解
问题描述
给定N台编号为0到N−1的网络设备，其中有一组大小为M的设备是互斥的——这M台设备之间任意两台都不能直接或间接相连。网络工程师收到X条连接指令，每条指令是将编号为 Cj 和Dj的两台设备连接。如果执行某条指令会导致在互斥设备子集中出现路径相连，则该指令被拒绝并计数，但仍继续处理后续指令。
请在所有指令执行完毕后，输出被拒绝执行的指令总数。
题目内容
在一个网络系统中，每台设备都有一个从 0 开始的唯一编号。系统内存在一组被标记为“互斥设备”的特殊设备。互斥规则要求：任意两台互斥设备之间都不能存在路径，既不允许它们被直接连接，也不允许它们通过其他设备间接连通。
网络工程师会按顺序处理若干条连接指令。每条指令会指定两台不同设备，要求在这两台设备之间建立直接连接。对于一条指令，如果执行后会使得至少一对互斥设备处于同一个连通块中，就说明触发了互斥规则，工程师会拒绝该指令并记录一次拒绝；否则，这条指令会被执行，网络连接状态随之更新。被拒绝的指令不会改变连接状态，也不会影响后续指令的判断。
请统计所有指令处理完毕后，被拒绝执行的指令总条数。
约束条件：
- 设备总数 N 满足 1≤N≤1000。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
