题解 洛谷 P7687 [CEOI2005] Critical Network Lines

P7687 [CEOI2005] Critical Network Lines

简要题意

给你一张图，图上有两类点 $A$ 和 $B$，现在要求你找到满足下面条件的边：删除这条边后该图变为两个块，且至少有一个块中只包含 $A$ 类点或只包含 $B$ 类点。

策略分析

前置芝士：割边（桥）

我们不难看出题目想让我们求的边是图中的割边，但并非所有的割边都满足题目的条件。如下图（图中边上的数字是编号不是边权）：

这幅图中的割边有 $1,4,5,6,8$ 五条，而符合题目条件的只有 $1,6,8$ 这三条。仔细考虑我们在深搜的时候形成的深度优先生成树的性质，我们发现，当一个割边满足条件当且仅当它连接的一个节点在深度优先生成树中的子树内只包含一类点（如果后面看不懂建议反复阅读体会这句话）。求割边的时候，每找到一条割边 $(u,v)$，我们就检查一下以 $v$ 为根结点的子树内 $A$ 和 $B$ 类结点各自的数量，当其中一个个数为 $0$ 或者全满，就是要求的边，打上标记并给计数的答案加一就可以了。求数量的过程，可以在 $\operatorname{dfs}$ 的时候递归计算。

实现

#include <iostream>
#include <cstdio>
using namespace std;

namespace SHAWN {
    const int N = 2e6 + 7;
    // 请注意这里一定要开二倍空间，要不然会寄
    int head[N], cnt;
    struct edge { int to, next; }edge[N];
    int n, m, a, b, tim, res;
    int dfn[N], low[N], acnt[N], bcnt[N], par[N];
    // acnt[i]表示i结点子树中A类点数量，bcnt同理
    // par用来记每个结点在dfs生成树中的父亲
    bool flag[N];

    inline void add(int u, int v) {
        edge[++cnt].next = head[u];
        edge[cnt].to = v;
        head[u] = cnt;
    }

    void Tarjan(int u, int fa) {
        low[u] = dfn[u] = ++tim;
        par[u] = fa;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (!dfn[v]) {
                Tarjan(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u]) {
                    if (!acnt[v] || !bcnt[v] || acnt[v] == a || bcnt[v] == b) {
                        // A类或B类有一个为0或全满就说明符合要求
                        flag[v] = true;
                        ++res;
                        // 后来看大家的做法这里用vector套一个pair存也非常方便
                    }
                }
                acnt[u] += acnt[v]; bcnt[u] += bcnt[v];
                // 从下向上递归统计子树情况
            }
            else if (dfn[v] < dfn[u] && fa != v) {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }
    int work()
    {
        cin >> n >> m >> a >> b;
        for (int i = 1, x; i <= a; ++i) { cin >> x; acnt[x] = 1; }
        for (int i = 1, x; i <= b; ++i) { cin >> x; bcnt[x] = 1; }
        // 最开始每个点的子树就是自己
        for (int i = 1, x, y; i <= m; ++i) {
            cin >> x >> y;
            add(x, y); add(y, x);
        }
        Tarjan(1, 0);
        cout << res << '\n';
        for (int i = 1; i <= n; ++i) {
            if (flag[i]) {
                cout << i << ' ' << par[i] << '\n';
            }
        }
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}