P4769 干扰者病毒（提高）

解题思路

通信网络可以看成一张无向图：基站是顶点，线路是边。"干扰者"病毒可以破坏一个基站，破坏后与它相连的所有线路都会被切断。但病毒有个怪脾气：如果两个相邻的基站都被放了病毒，它们就会打起来产生冲突。我们要找出：最少放多少个病毒，能切断所有线路，又不会让任意两个病毒所在的基站相邻。这道题的关键是看懂它其实是一道"二分图判定"题，分成几步：

1. 第一步，把两个条件翻译成"每条边恰好一个端点放病毒"。 "切断所有线路"意味着每条边至少有一个端点被放病毒；"避免冲突"又意味着每条边不能两个端点都被放病毒。合起来就是：每条边的两个端点中，恰好有一个放病毒。

2. 第二步，联想到二分图染色。 "每条边的两个端点恰好一个放病毒"正好等价于把图的顶点染成两种颜色（黑和白），相邻的两个顶点颜色必须不同——这正是判定图是不是"二分图"。

3. 第三步，用 BFS 染色检查，并统计答案。 从任意一个顶点出发做 BFS：把它染成颜色 0，相邻顶点染颜色 1，再继续往下染。如果某个顶点的相邻顶点已经被染过、而且颜色和自己一样，就说明存在"一条边的两个端点同色"的情况，图不是二分图，根本做不到题目要求，输出 Impossible。如果整张图都染色成功，那么每个连通块里，选"颜色 0 的个数"和"颜色 1 的个数"中较小的那个，就能切断这个连通块的所有边且不冲突，把每个连通块的最小值加起来，就是答案。

4. 第四步，用样例验证。 3 个基站，边是 1-2、1-3、2-3，这是个三角形。从 1 开始染色，1 染 0，2、3 染 1；再看 2 和 3 相邻却都是颜色 1，冲突了，所以不是二分图，输出 Impossible，和样例一致。

5. 第五步，写代码的注意点。 用邻接表存图，用一个 color 数组记录颜色（-1 表示还没染色），用数组模拟队列做 BFS。n 比较大时，邻接表和队列都要按 n 开足够大。

参考代码

// 干扰者病毒：二分图判定。能切断全部线路且病毒不相邻，等价于给图染两种颜色，
// 同一条边的两端必须颜色不同。若不是二分图则 Impossible，否则答案取每部分较小颜色数之和
#include <iostream>
#include <vector>
int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int> > graph(n + 1); // 邻接表存图
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    std::vector<int> color(n + 1, -1); // color[i]：-1 表示还没染色，0/1 是两种颜色
    std::vector<int> queue(n + 1);     // 用数组模拟队列做 BFS
    int answer = 0;
    bool isBipartite = true;
    for (int start = 1; start <= n && isBipartite; ++start) {
        if (color[start] != -1) continue; // 已经在别的连通块染过色
        int front = 0, rear = 0;
        queue[rear++] = start;
        color[start] = 0;
        int color0Count = 0, color1Count = 0; // 统计颜色0、颜色1的顶点个数
        while (front < rear) {
            int u = queue[front++];
            if (color[u] == 0) ++color0Count; else ++color1Count;
            for (size_t i = 0; i < graph[u].size(); ++i) {
                int v = graph[u][i];
                if (color[v] == -1) {
                    color[v] = 1 - color[u]; // 相邻顶点染相反颜色
                    queue[rear++] = v;
                } else if (color[v] == color[u]) {
                    isBipartite = false; // 相邻顶点同色，说明不是二分图
                }
            }
        }
        answer += (color0Count < color1Count ? color0Count : color1Count); // 这一部分选较少的那种颜色
    }
    if (!isBipartite) std::cout << "Impossible\n";
    else std::cout << answer << '\n';
    return 0;
}

复杂度分析

BFS 染色会访问每个顶点和每条边各一次，所以判断二分图的时间复杂度是 O(n+m)，空间复杂度是 O(n+m)（邻接表存图加 color、队列数组）。n 和 m 最多几十万时，运行也很快。这道题的难点在于把"病毒不相邻 + 切断所有边"转化成二分图染色问题，掌握了这个转化，实现本身并不复杂。