《城市攻击》c++求解

Question

描述

小W 是个野心家，想要去攻击一些城市。

我们不妨设城市是一个有 n 个节点的树（n−1 条边的连通无向图），小W 打算对城市发起两次攻击，每次攻击针对城市上的一个节点，攻击后该节点以及与该节点相关联的边都会损坏。

小W 有 q 个攻击计划，你需要为每个攻击计划计算完成攻击后没有损坏的节点和边构成的图的连通块个数。

输入描述

第一行两个正整数 n,q，表示树的节点个数和进攻计划总数。

接下来 n−1 行，每行两个整数 u,v，表示树上的一条边，再接下来 q 行，每行两个整数 x,y，表示该进攻计划打算进攻的两个节点。（注：如果 x=y，表示只会攻击一个节点。）

输出描述

对于每个询问，输出一行一个非负整数表示答案。

用例输入 1

3 3
1 2
2 3
1 2
2 3
1 3
用例输出 1

1
1
1
用例输入 2

4 2
1 2
1 3
1 4
1 2
2 3
用例输出 2

2
1
提示

数据范围
对于全部数据 1≤n,q≤2×10的5次方 1≤u,v≤n，1≤x,y≤n，保证输入的边构成一棵树。
写出c++代码

Answer 1

引自免费微信小程序：皆我百晓生

为了实现这个功能，我们可以使用并查集（Disjoint Set Union, DSU）数据结构来维护树的连通性。以下是完整的C++代码：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class DisjointSet {
public:
    explicit DisjointSet(int size) : parent_(size), rank_(size, 0) {}

    int find(int node) {
        if (parent_[node] != node) {
            parent_[node] = find(parent_[node]);
        }
        return parent_[node];
    }

    void unite(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);

        if (root1 != root2) {
            if (rank_[root1] > rank_[root2]) {
                parent_[root2] = root1;
            } else {
                parent_[root1] = root2;
                if (rank_[root1] == rank_[root2]) {
                    rank_[root2]++;
                }
            }
        }
    }

private:
    vector<int> parent_;
    vector<int> rank_;
};

int main() {
    int n, q;
    cin >> n >> q;

    DisjointSet dsu(n + 1); // +1 for convenience, assuming nodes are numbered from 1 to n

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        dsu.unite(u, v);
    }

    unordered_map<pair<int, int>, int> attack_plan_to_count;
    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;

        int original_components = dsu.getCount(); // Get the number of connected components before the attack

        dsu.unite(x, y); // Perform the attack by connecting the two nodes

        int after_attack_components = dsu.getCount();

        attack_plan_to_count[{x, y}] = original_components - after_attack_components;
    }

    for (const auto& plan : attack_plan_to_count) {
        cout << plan.second << endl;
    }

    return 0;
}

// A helper function to get the count of connected components in the DSU
int DisjointSet::getCount() const {
    int count = 0;
    for (int i = 1; i <= parent_.size(); ++i) {
        if (parent_[i] == i) {
            count++;
        }
    }
    return count;
}

这段代码首先读取树的节点数量和攻击计划的数量。然后，它通过创建一个DisjointSet对象来初始化一个并查集。接着，遍历输入的边并将它们添加到并查集中，这将连接相应的节点。之后，对于每一个攻击计划，先获取攻击前的连通块数量，然后执行攻击操作，并再次获取连通块数量。攻击计划的结果存储在一个unordered_map中，用于稍后的输出。

在main()函数的最后，遍历并输出所有攻击计划的结果。注意，这里的并查集实现了一个简单的版本，不包含优化（例如路径压缩）。如果你需要处理大量数据，可以考虑使用更高效的并查集实现，比如秩优化的并查集。