[USACO16OPEN] Closing the Farm G

题意

给一张无向图，顶点表示谷仓，边表示道路。

接下来会按给定顺序一个一个关闭谷仓。每次都要回答：

在当前这一次关闭之前
还开着的所有谷仓是否两两连通

也就是当前农场是否仍然是“全连通”的。

思路

先看一个小数据暴力：

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, m;
vector<int> graph[MAXN];
int close_order[MAXN];
bool alive[MAXN];
bool vis[MAXN];

bool check_connected() {
    int start = 0;
    for (int i = 1; i <= n; i++) {
        if (alive[i]) {
            start = i;
            break;
        }
    }

    if (start == 0) {
        return true;
    }

    for (int i = 1; i <= n; i++) {
        vis[i] = false;
    }

    queue<int> q;
    q.push(start);
    vis[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : graph[u]) {
            if (!alive[v] || vis[v]) {
                continue;
            }
            vis[v] = true;
            q.push(v);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (alive[i] && !vis[i]) {
            return false;
        }
    }
    return true;
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        graph[i].clear();
        alive[i] = true;
    }

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

    for (int i = 1; i <= n; i++) {
        cin >> close_order[i];
    }

    for (int i = 1; i <= n; i++) {
        cout << (check_connected() ? "YES" : "NO") << '\n';
        alive[close_order[i]] = false;
    }

    return 0;
}

暴力的想法很直接：

维护哪些谷仓还开着
每次关闭之前做一次 BFS/DFS
检查所有还开着的点是否在同一个连通块里

这个写法可以帮助理解题意，但如果每次都重新搜整张图，复杂度太高。

关键观察是：关闭操作不好维护，但把过程倒过来就很好维护。

原问题是：

一开始所有谷仓都开着
然后不断关闭

倒过来看就是：

一开始所有谷仓都关着
按关闭顺序的逆序，一个一个重新打开

这样每次“打开”一个谷仓时，只需要把它和当前已经开着的相邻谷仓并查集合并即可。

于是我们维护：

$open[u]$ ：谷仓 $u$ 当前是否已经被重新打开
components：当前开着的谷仓形成了多少个连通块

每次倒序打开一个点 $u$ ：

先把 $components++$ ，因为新开了一个独立点
枚举它所有邻居 $v$
如果 $v$ 也开着，并且它们原来不在同一个集合，就合并，并让 $components--$

这样当这一轮处理结束后：

如果 $components == 1$ ，说明当前所有开着的谷仓全连通

再把这个答案倒回原顺序输出即可。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n, m;
vector<int> graph[MAXN];
int close_order[MAXN];
bool open_[MAXN];
bool ans[MAXN];

struct DSU {
    int fa[MAXN], sz[MAXN];

    void init(int n) {
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
            sz[i] = 1;
        }
    }

    int find(int x) {
        if (fa[x] == x) {
            return x;
        }
        fa[x] = find(fa[x]);
        return fa[x];
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] < sz[y]) {
            swap(x, y);
        }
        fa[y] = x;
        sz[x] += sz[y];
        return true;
    }
} dsu;

void read_input() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        graph[i].clear();
        open_[i] = false;
    }

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

    for (int i = 1; i <= n; i++) {
        cin >> close_order[i];
    }
}

void solve() {
    dsu.init(n);

    int components = 0; // 当前开着的谷仓形成了多少个连通块
    for (int i = n; i >= 1; i--) {
        int u = close_order[i];
        open_[u] = true;
        components++;

        for (int v : graph[u]) {
            if (!open_[v]) {
                continue;
            }
            if (dsu.unite(u, v)) {
                components--;
            }
        }

        ans[i] = (components == 1);
    }
}

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

    read_input();
    solve();

    for (int i = 1; i <= n; i++) {
        cout << (ans[i] ? "YES" : "NO") << '\n';
    }

    return 0;
}

复杂度

设点数为 $n$ ，边数为 $m$ 。

每条边最多在倒序加入时检查两次
并查集合并与查询均摊近似常数

总时间复杂度 $O((n + m)\alpha(n))$ ，空间复杂度 $O(n + m)$ 。

总结

这题的典型点在于“删点难，倒序加点容易”。一旦把关闭过程翻过来看，问题就变成了并查集维护动态图连通块数量的标准模型。

一图流解析

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

[USACO16OPEN] Closing the Farm G

目录

题意

思路

代码

复杂度

总结

一图流解析