题解

问题描述

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

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

思路分析

1. 使用并查集维护各设备的连通分量。

2. 初始时，任意设备都是独立的。

3. 对于每条指令$(C_j, D_j)$，

   • 先在并查集中查询$C_j$和$D_j$的根节点$r_C$、$r_D$。

   • 如果将这条边加入，会令某互斥设备子集中存在两台设备连通，则拒绝：

     1. 预先将互斥设备列表中每台设备的根记录下来，或维护一个集合$S$，对该集合中的根做标记。
     2. 若连接后$r_C$ 与 $r_D$ 中至少有一个已标记为互斥设备所在根，且合并后会造成两个不同的互斥根合并，则拒绝。

   • 否则合并$r_C$ 与$r_D$，并更新标记信息。

4. 统计拒绝次数即可。

cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int parent[MAXN], sz[MAXN];
bool blocked[MAXN]; // 标记并查集根是否覆盖互斥设备子集

// 并查集初始化
int findp(int x) {
    return parent[x] == x ? x : parent[x] = findp(parent[x]);
}

void unite(int a, int b) {
    a = findp(a);
    b = findp(b);
    if (a == b) return;
    // 按大小合并
    if (sz[a] < sz[b]) swap(a, b);
    parent[b] = a;
    sz[a] += sz[b];
    // 如果其中一个集合是互斥设备集，合并后保持标记
    blocked[a] = blocked[a] || blocked[b];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, X;
    cin >> N >> M >> X;
    vector<int> A(M);
    for (int i = 0; i < N; i++) {
        parent[i] = i;
        sz[i] = 1;
        blocked[i] = false;
    }
    for (int i = 0; i < M; i++) {
        cin >> A[i];
    }
    // 将互斥设备标记到各自根
    for (int v : A) {
        blocked[findp(v)] = true;
    }

    int reject = 0;
    while (X--) {
        int u, v;
        cin >> u >> v;
        int ru = findp(u);
        int rv = findp(v);
        // 若两个集合都已有互斥标记，且不在同一集合，则拒绝
        if (ru != rv && blocked[ru] && blocked[rv]) {
            reject++;
        } else {
            unite(ru, rv);
        }
    }
    cout << reject;
    return 0;
}

python

# 并查集实现
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.sz = [1] * n
        self.blocked = [False] * n  # 互斥标记

    def findp(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.findp(self.parent[x])
        return self.parent[x]

    def unite(self, a, b):
        a = self.findp(a)
        b = self.findp(b)
        if a == b:
            return
        if self.sz[a] < self.sz[b]:
            a, b = b, a
        self.parent[b] = a
        self.sz[a] += self.sz[b]
        self.blocked[a] = self.blocked[a] or self.blocked[b]


def main():
    import sys
    data = sys.stdin.read().split()
    N, M, X = map(int, data[:3])
    A = list(map(int, data[3:3+M]))
    ops = list(map(int, data[3+M:]))

    dsu = DSU(N)
    # 标记互斥设备根
    for v in A:
        dsu.blocked[dsu.findp(v)] = True

    rejects = 0
    idx = 0
    for _ in range(X):
        u, v = ops[idx], ops[idx+1]
        idx += 2
        ru, rv = dsu.findp(u), dsu.findp(v)
        if ru != rv and dsu.blocked[ru] and dsu.blocked[rv]:
            rejects += 1
        else:
            dsu.unite(ru, rv)
    print(rejects)

if __name__ == '__main__':
    main()

java

import java.io.*;
import java.util.*;

public class Main {
    static int[] parent, sz;
    static boolean[] blocked;

    static int findp(int x) {
        if (parent[x] != x) {
            parent[x] = findp(parent[x]);
        }
        return parent[x];
    }

    static void unite(int a, int b) {
        a = findp(a);
        b = findp(b);
        if (a == b) return;
        if (sz[a] < sz[b]) {
            int t = a; a = b; b = t;
        }
        parent[b] = a;
        sz[a] += sz[b];
        blocked[a] = blocked[a] || blocked[b];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        parent = new int[N]; sz = new int[N]; blocked = new boolean[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            sz[i] = 1;
            blocked[i] = false;
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int v = Integer.parseInt(st.nextToken());
            blocked[findp(v)] = true;
        }

        int rejects = 0;
        for (int i = 0; i < X; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int ru = findp(u), rv = findp(v);
            if (ru != rv && blocked[ru] && blocked[rv]) {
                rejects++;
            } else {
                unite(ru, rv);
            }
        }
        System.out.println(rejects);
    }
}

题目内容

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

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

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

输入描述

$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]$。