DDOSvoid's Blog

Luogu P5227 [AHOI2013]连通图

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P5227

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图以及 $k$ 个大小不超过 $4$ 的集合，每个集合内有若干条边，求对于每个集合，如果去掉集合内的边，图是否连通

$n,k\le 10^5,m\le 2\times 10^5$

Solution

我们考虑一种比较特殊的分治，我们令 $solve(l,r)$ 表示 $[l,r]$ 中的边还没加

然后加上并查集的撤销操作，在递归底层统计答案即可

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define maxn 100010
#define maxm 200010
using namespace std;

int n, m, k;

struct Edge {
    int fr, to;
} e[maxm];

int fa[maxn], sz[maxn], st[maxn], top;
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1; } 

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

inline void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return ;
    if (sz[fx] > sz[fy]) swap(fx, fy);
    st[++top] = fx; fa[fx] = fy; sz[fy] += sz[fx];
}

inline void undo(int _top) {
    while (top > _top) {
        int t = st[top--];
        sz[fa[t]] -= sz[t]; fa[t] = t;
    }
}

vector<int> A[maxm]; int ans[maxm], use[maxm]; int _cnt;
void solve(int l, int r) {
    if (l == r) return (void) (ans[l] = sz[find(1)] == n);
    int m = l + r >> 1, _top = top; ++_cnt;
    for (int i = m + 1; i <= r; ++i)
        for (auto u : A[i]) use[u] = _cnt; 
    for (int i = l; i <= m; ++i)
        for (auto u : A[i]) if (use[u] ^ _cnt) merge(e[u].fr, e[u].to); 
    solve(m + 1, r); undo(_top); ++_cnt; _top = top;
    for (int i = l; i <= m; ++i)
        for (auto u : A[i]) use[u] = _cnt; 
    for (int i = m + 1; i <= r; ++i)
        for (auto u : A[i]) if (use[u] ^ _cnt) merge(e[u].fr, e[u].to);
    solve(l, m); undo(_top);
} 

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

    cin >> n >> m; init_fa(n); memset(use, -1, sizeof use); 
    for (int i = 1; i <= m; ++i) cin >> e[i].fr >> e[i].to;
    cin >> k; 
    for (int i = 1; i <= k; ++i) {
        int x, y; cin >> x;
        while (x--) cin >> y, A[i].push_back(y), use[y] = 0;;
    }
    for (int i = 1; i <= m; ++i) if (use[i] == -1) merge(e[i].fr, e[i].to);
    solve(1, k);
    for (int i = 1; i <= k; ++i)
        ans[i] ? cout << "Connected" << "\n" : cout << "Disconnected" << "\n"; 
    return 0;
}