[CEOI 2005] Critical Network Lines

题意

给一张连通无向图。

有些点提供 A 服务，有些点提供 B 服务，一个点可以同时提供两种服务。

如果删掉某条边以后，出现下面情况：

存在某个点，无法到达任意一个 A 服务点
或者无法到达任意一个 B 服务点

那么这条边就叫关键通信线路。

要求输出：

关键通信线路的数量
每条关键通信线路对应的两个端点

原题有 Special Judge，所以答案边的输出顺序、以及同一条边两个端点的先后顺序，都不唯一。本仓库为了让 check_sample.py 做精确比对，固定采用“按输入边方向输出”的一种合法格式。

样例图

这张图展示样例中的主干结构：

graph G {
  1 -- 2;
  1 -- 4;
  2 -- 4;
  2 -- 3 [color=red, penwidth=2];
  1 -- 5;
  5 -- 6 [color=red, penwidth=2];
  6 -- 7;
  6 -- 8;
  7 -- 8;
  7 -- 9 [color=red, penwidth=2];
}

红色边都是桥，但并不是所有桥都一定是答案。真正关键的是：删掉它之后，某一侧会不会缺少 A 或 B 服务。

思路

先看一个最直接的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102// brute.cpp：枚举删掉哪一条边，然后直接检查每个连通块是否同时拥有 A/B 两种服务。
// 这是最贴近题意的暴力验证版，只适合小数据对拍。
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
} edges[105];

int n, m, cnt_a, cnt_b;
bool has_a[25], has_b[25];
vector<int> g[25];
bool vis[25];

void build_graph(int ban) {
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        vis[i] = false;
    }

    for (int i = 1; i <= m; i++) {
        if (i == ban) {
            continue;
        }
        int u = edges[i].u;
        int v = edges[i].v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void dfs(int u, int &cnt_node, int &cnt_service_a, int &cnt_service_b) {
    vis[u] = true;
    cnt_node++;
    cnt_service_a += has_a[u];
    cnt_service_b += has_b[u];

    for (size_t i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!vis[v]) {
            dfs(v, cnt_node, cnt_service_a, cnt_service_b);
        }
    }
}

bool is_critical(int ban) {
    build_graph(ban);

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            int cnt_node = 0;
            int cnt_service_a = 0;
            int cnt_service_b = 0;
            dfs(i, cnt_node, cnt_service_a, cnt_service_b);

            if (cnt_service_a == 0 || cnt_service_b == 0) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> cnt_a >> cnt_b;

    memset(has_a, 0, sizeof(has_a));
    memset(has_b, 0, sizeof(has_b));

    for (int i = 1; i <= cnt_a; i++) {
        int x;
        cin >> x;
        has_a[x] = true;
    }
    for (int i = 1; i <= cnt_b; i++) {
        int x;
        cin >> x;
        has_b[x] = true;
    }

    for (int i = 1; i <= m; i++) {
        cin >> edges[i].u >> edges[i].v;
    }

    vector<int> answer;
    for (int i = 1; i <= m; i++) {
        if (is_critical(i)) {
            answer.push_back(i);
        }
    }

    cout << answer.size() << '\n';
    for (size_t i = 0; i < answer.size(); i++) {
        int id = answer[i];
        cout << edges[id].u << ' ' << edges[id].v << '\n';
    }

    return 0;
}

暴力做法完全按题意来：

枚举删掉哪一条边
重新求删边后的连通块
看是否存在某个连通块没有 A 服务，或者没有 B 服务

这个思路很好理解，但每删一条边都要重跑一遍 DFS，复杂度太高。

正式做法先抓住第一层关键性质：

只有桥才可能成为答案

因为如果一条边不是桥，删掉它以后图仍然连通，所有点还能访问原来的所有服务，自然不可能出问题。

所以问题就缩小成：

枚举每一条桥
判断删掉这条桥以后，两侧是否都同时含有 A 和 B

设 DFS 树上一条桥是 u - v，其中 v 是 u 的儿子。删掉这条桥以后，图会被分成两部分：

v 的整棵 DFS 子树
其余所有点

这时只要维护：

sub_a[v]：v 子树里有多少个 A 服务点
sub_b[v]：v 子树里有多少个 B 服务点

另一侧的数量就是：

total_a - sub_a[v]
total_b - sub_b[v]

于是桥 u-v 是关键线路，当且仅当下面四个数里有一个为 0：

sub_a[v]
sub_b[v]
total_a - sub_a[v]
total_b - sub_b[v]

也就是删桥后的某一侧缺少了至少一种服务。

实现上，我把“找桥”和“统计子树服务数量”合在同一遍 DFS 里做完。因为这题不需要根节点特判，所以写法比割点、点双还更直接。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159#include <bits/stdc++.h>
using namespace std;

struct Frame {
    int u;
    int in_edge;
    int iter_edge;
};

int n, m, cnt_a, cnt_b;
int total_a, total_b;

vector<int> service_a, service_b;
vector<int> head, to, nxt, edge_id;
vector<int> eu, ev;

vector<int> dfn, low, parent_node, parent_edge;
vector<int> sub_a, sub_b;
vector<int> answer_flag;

int edge_cnt;
int dfs_clock;

void add_edge(int u, int v, int id) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    edge_id[edge_cnt] = id;
    head[u] = edge_cnt;
}

// 非递归 Tarjan 找桥，同时统计每棵 DFS 子树中的 A/B 服务点数量。
void solve_component(int start) {
    vector<Frame> st;
    st.push_back({start, 0, head[start]});

    dfn[start] = low[start] = ++dfs_clock;
    sub_a[start] = service_a[start];
    sub_b[start] = service_b[start];

    while (!st.empty()) {
        Frame &cur = st.back();
        int u = cur.u;

        if (cur.iter_edge != 0) {
            int e = cur.iter_edge;
            cur.iter_edge = nxt[e];
            int v = to[e];

            if (e == (cur.in_edge ^ 1)) {
                continue;
            }

            if (!dfn[v]) {
                parent_node[v] = u;
                parent_edge[v] = e;

                dfn[v] = low[v] = ++dfs_clock;
                sub_a[v] = service_a[v];
                sub_b[v] = service_b[v];

                st.push_back({v, e, head[v]});
                continue;
            }

            if (dfn[v] < dfn[u]) {
                low[u] = min(low[u], dfn[v]);
            }
            continue;
        }

        st.pop_back();

        if (cur.in_edge != 0) {
            int p = parent_node[u];

            sub_a[p] += sub_a[u];
            sub_b[p] += sub_b[u];
            low[p] = min(low[p], low[u]);

            if (low[u] > dfn[p]) {
                int other_a = total_a - sub_a[u];
                int other_b = total_b - sub_b[u];

                if (sub_a[u] == 0 || sub_b[u] == 0 || other_a == 0 || other_b == 0) {
                    answer_flag[edge_id[cur.in_edge]] = 1;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> cnt_a >> cnt_b;

    service_a.assign(n + 1, 0);
    service_b.assign(n + 1, 0);

    for (int i = 1; i <= cnt_a; i++) {
        int x;
        cin >> x;
        service_a[x] = 1;
    }
    for (int i = 1; i <= cnt_b; i++) {
        int x;
        cin >> x;
        service_b[x] = 1;
    }

    total_a = cnt_a;
    total_b = cnt_b;

    head.assign(n + 1, 0);
    to.assign(2 * m + 5, 0);
    nxt.assign(2 * m + 5, 0);
    edge_id.assign(2 * m + 5, 0);
    eu.assign(m + 1, 0);
    ev.assign(m + 1, 0);

    edge_cnt = 1;

    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        add_edge(eu[i], ev[i], i);
        add_edge(ev[i], eu[i], i);
    }

    dfn.assign(n + 1, 0);
    low.assign(n + 1, 0);
    parent_node.assign(n + 1, 0);
    parent_edge.assign(n + 1, 0);
    sub_a.assign(n + 1, 0);
    sub_b.assign(n + 1, 0);
    answer_flag.assign(m + 1, 0);

    dfs_clock = 0;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            solve_component(i);
        }
    }

    int answer_cnt = 0;
    for (int i = 1; i <= m; i++) {
        answer_cnt += answer_flag[i];
    }

    cout << answer_cnt << '\n';
    for (int i = 1; i <= m; i++) {
        if (answer_flag[i]) {
            cout << eu[i] << ' ' << ev[i] << '\n';
        }
    }

    return 0;
}

复杂度

每个点访问一次，每条边只会被常数次处理，所以：

时间复杂度 $O(n+m)$
空间复杂度 $O(n+m)$

总结

这题的主线非常清楚：

先把答案缩到“只有桥才可能出事”
再把“删桥后会不会缺服务”翻译成桥两侧的 A/B 数量判断

因此它本质上就是：

Tarjan 求桥
DFS 子树计数

一旦把这两件事接起来，判定条件就只剩下四个数量里是否出现 0。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[CEOI 2005] Critical Network Lines

目录

题意

样例图

思路

代码

复杂度

总结

一图流解析