Logo wfirstzhang的博客

博客

#411. C计划 题目资源

2025-09-19 19:23:26 By wfirstzhang

411std

#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 1000000;
const int MAXT = 2 * MAXN;

int n, m, Q;
vector<int> G[MAXN + 5];
vector<int> T[MAXT + 5];
int dfn[MAXN + 5], low[MAXN + 5];
int stk[MAXN + 5], top;
int idx, bcc_cnt;
int comp[MAXT + 5];
int depth[MAXT + 5], sum[MAXT + 5];
int fa[MAXT + 5][21];
int LOG;

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    for (int tmp = 0; tmp < G[u].size(); tmp++) {
        int v = G[u][tmp];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                bcc_cnt++;
                int w;
                do {
                    w = stk[top--];
                    T[bcc_cnt + n].push_back(w);
                    T[w].push_back(bcc_cnt + n);
                } while (w != v);
                T[bcc_cnt + n].push_back(u);
                T[u].push_back(bcc_cnt + n);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfs(int u, int father, int comp_id) {
    comp[u] = comp_id;
    depth[u] = depth[father] + 1;
    sum[u] = sum[father] + (u <= n ? 1 : 0);
    fa[u][0] = father;
    for (int i = 1; i <= LOG; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int tmp = 0; tmp < T[u].size(); tmp++) {
        int v = T[u][tmp];
        if (v == father) continue;
        dfs(v, u, comp_id);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG; i >= 0; i--) {
        if (depth[fa[u][i]] >= depth[v]) {
            u = fa[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LOG; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int main() {
    scanf("%d%d%d", &n, &m, &Q);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    idx = 0;
    top = 0;
    bcc_cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
            if (top > 0) {
                top--;
            }
        }
    }

    LOG = ceil(log2(n + bcc_cnt));
    for (int i = 1; i <= n; i++) {
        if (comp[i] == 0) {
            dfs(i, 0, i);
        }
    }

    while (Q--) {
        int S, T;
        scanf("%d%d", &S, &T);
        if (S == T) {
            printf("0\n");
        } else if (comp[S] != comp[T]) {
            printf("%d\n", n - 2);
        } else {
            int L = lca(S, T);
            int total = sum[S] + sum[T] - 2 * sum[L] + (L <= n ? 1 : 0);
            printf("%d\n", total - 2);
        }
    }

    return 0;
}

411val

#include "testlib.h"
#include <set>

int main(void) {
    using namespace std;
    registerValidation();
    int n, m, q;
    n = inf.readInt(1, 100000, "N");
    inf.readSpace();
    m = inf.readInt(1, 100000, "M");
    inf.readSpace();
    q = inf.readInt(1, 100000, "Q");
    inf.readEoln();
    set<pair<int, int> > visit;
    while(m--)
    {
        int u, v;
        u = inf.readInt(1, n, "u");
        v = inf.readInt(1, n, "v");
        ensuref(u != v, "u == v");
        if(u > v)
            swap(u, v);
        ensuref(visit.find(make_pair(u, v)) == visit.end(), "found {u, v}");
        visit.insert(make_pair(u, v)); 
        inf.readEoln();
    }
    while(q--)
    {
        int s, t;
        s = inf.readInt(1, n, "S");
        t = inf.readInt(1, n, "T");
        ensuref(s != t, "S == T");
        inf.readEoln();
    }
    inf.readEof();
    return 0;
}

411edtr

题目大意

给定一个无向图，多次询问，每次询问给出两个点 $S$ 和 $T$，求有多少个点 $v$（$v \neq S$ 且 $v \neq T$）满足删除 $v$ 后 $S$ 和 $T$ 不再连通。

算法思路

本问题的核心在于找出图中所有能够断开 $S$ 和 $T$ 的连接的点，即 $S$ 和 $T$ 之间的必经点。为了解决这个问题，我们使用圆方树（Block-Cut Tree）来高效地识别这些必经点。

圆方树构建

  1. 点双连通分量（BCC）识别：

    • 使用 Tarjan 算法识别图中的所有点双连通分量。
    • 每个点双连通分量对应圆方树中的一个方点，原图中的点对应圆点。

  2. 圆方树构建：

    • 对于每个点双连通分量，创建一个方点，并将该方点与点双中的所有圆点连接。
    • 圆方树中的边连接方点和圆点，表示圆点属于对应的点双连通分量。

查询处理

  1. 连通性判断：

    • 如果 $S$ 和 $T$ 不在同一个连通分量中，则删除任何点都无法使它们连通，因此答案为 $n-2$。
    • 如果 $S$ 和 $T$ 相同，则没有点可以删除，答案为 $0$。

  2. 必经点计算：

    • 对于在同一个连通分量中的 $S$ 和 $T$，计算它们在圆方树路径上的圆点数量。
    • 使用最近公共祖先（LCA）技术快速计算路径上的圆点数量。
    • 答案即为路径上的圆点数量减去 $2$（排除 $S$ 和 $T$）。

算法正确性证明

圆方树的性质

  • 圆方树中的圆点代表原图中的节点，方点代表点双连通分量。
  • 在圆方树中，两个圆点之间的路径上的圆点就是原图中这两个点之间的所有必经点。
  • 这是因为点双连通分量内部存在多条路径，只有割点才是连接不同分量的关键点。

计算正确性

  • 对于查询 $S$ 和 $T$，如果它们不在同一个连通分量中，那么无论删除哪个点，它们仍然不连通，因此所有点（除 $S$ 和 $T$ 外）都满足条件。
  • 如果 $S$ 和 $T$ 在同一个连通分量中，那么只有路径上的圆点（必经点）才会影响它们的连通性。计算路径上的圆点数量并排除 $S$ 和 $T$，即可得到正确的答案。

复杂度分析

  • 时间复杂度：

    • Tarjan 算法和圆方树构建的时间复杂度为 $O(n + m)$。
    • LCA 预处理和查询的时间复杂度为 $O(n \log n + q \log n)$。
    • 总体时间复杂度为 $O((n + m) + q \log n)$，适用于大规模数据。

  • 空间复杂度：

    • 存储图和圆方树的空间复杂度为 $O(n + m)$。
    • LCA 预处理的空间复杂度为 $O(n \log n)$。

代码实现

#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 1000000;
const int MAXT = 2 * MAXN;

int n, m, Q;
vector<int> G[MAXN + 5];
vector<int> T[MAXT + 5];
int dfn[MAXN + 5], low[MAXN + 5];
int stk[MAXN + 5], top;
int idx, bcc_cnt;
int comp[MAXT + 5];
int depth[MAXT + 5], sum[MAXT + 5];
int fa[MAXT + 5][21];
int LOG;

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    for (int v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                bcc_cnt++;
                int w;
                do {
                    w = stk[top--];
                    T[bcc_cnt + n].push_back(w);
                    T[w].push_back(bcc_cnt + n);
                } while (w != v);
                T[bcc_cnt + n].push_back(u);
                T[u].push_back(bcc_cnt + n);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfs(int u, int father, int comp_id) {
    comp[u] = comp_id;
    depth[u] = depth[father] + 1;
    sum[u] = sum[father] + (u <= n ? 1 : 0);
    fa[u][0] = father;
    for (int i = 1; i <= LOG; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int v : T[u]) {
        if (v == father) continue;
        dfs(v, u, comp_id);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG; i >= 0; i--) {
        if (depth[fa[u][i]] >= depth[v]) {
            u = fa[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LOG; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int main() {
    scanf("%d%d%d", &n, &m, &Q);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    idx = 0;
    top = 0;
    bcc_cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    LOG = ceil(log2(n + bcc_cnt));
    for (int i = 1; i <= n; i++) {
        if (comp[i] == 0) {
            dfs(i, 0, i);
        }
    }

    while (Q--) {
        int S, T;
        scanf("%d%d", &S, &T);
        if (S == T) {
            printf("0\n");
        } else if (comp[S] != comp[T]) {
            printf("%d\n", n - 2);
        } else {
            int L = lca(S, T);
            int total = sum[S] + sum[T] - 2 * sum[L] + (L <= n ? 1 : 0);
            printf("%d\n", total - 2);
        }
    }

    return 0;
}

总结

本题解通过构建圆方树和利用 LCA 技术，高效地解决了图中必经点查询问题。算法正确性基于圆方树的性质，能够快速计算任意两点之间的必经点数量，适用于大规模数据输入。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

鲁ICP备2025150228号

Server Time: 2025-10-29 06:25:56 | OpenSource Project