题解：P11545 [Code+#5] 割集确定

lzx111218 · 2025-01-11 12:12:01 · 题解

思路

看了看这题的题解，突然心血来潮想用 链式前向星 来做。

链式前向星可以在邻接表的基础上减少空间浪费，并且加速图的遍历。谁还用 vector 啊用两个数组来表示图：

• hd[]：记录每个节点的边的起始位置。
• nx[] 和 t[]：通过这两个数组表示边的连接关系，nx[] 用来连接同一节点的多条边，t[] 则记录目标节点。

DFS

用 DFS 从任意节点开始遍历，计算每个城市的 子树大小。DFS 的过程中，我们需要记录每个节点的父节点，并计算每个子树的大小，用数组 sz[] 来存储每个节点的子树大小。

void dfs(int u) {
    sz[u] = 1;
    for (int i = hd[u]; i != -1; i = nx[i]) {
        int v = t[i];
        if (f[v] == -1) {
            f[v] = u;
            dfs(v);
            sz[u] += sz[v];
        }
    }
}

还有事件处理，需要分析给定的错误信息，根据错误信息来判断哪些节点的情报中心失效：

• 如果某条边的两个城市都无法通信，可以通过父子关系来更新失效的节点数。
• 对于每个事件，就去检查错误信息，再去根据父子关系来调整被歼灭的节点数量。

因为这个才 WA 了五次。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, q, a;
vector<pair<int, int>> p;
vector<int> t, nx, hd, sz, f, e;
void dfs(int u) {
    sz[u] = 1;
    for (int i = hd[u]; i != -1; i = nx[i]) {
        int v = t[i];
        if (f[v] == -1) {
            f[v] = u;
            dfs(v);
            sz[u] += sz[v];
        }
    }
}

signed main() {
    scanf("%lld %lld", &n, &m);
    hd.resize(n + 1, -1); 
    sz.resize(n + 1);
    f.resize(n + 1, -1);
    t.resize(2 * m + 1); 
    nx.resize(2 * m + 1);
    int ed = 0;

    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%lld %lld", &u, &v);

        t[ed] = v;
        nx[ed] = hd[u];
        hd[u] = ed++;

        t[ed] = u;
        nx[ed] = hd[v];
        hd[v] = ed++;

        p.push_back({u, v});
    }

    f[1] = -1;
    dfs(1);

    scanf("%lld", &q);
    while (q--) {
        a = 0;
        int c;
        scanf("%lld", &c);
        while (c--) {
            int o, u, v;
            scanf("%lld", &o);
            if (o > 0) {
                u = p[o - 1].first;
                v = p[o - 1].second;
            } else {
                u = p[-o - 1].second;
                v = p[-o - 1].first;
            }

            if (f[u] == v) {
                a -= sz[u];
            }
            if (f[v] == u) {
                a += sz[v];
            }
        }

        if (a < 0) {
            a += n;
        }

        printf("%lld\n", a);
    }

    return 0;
}