DDOSvoid's Blog

bzoj 3569 DZY Loves Chinese II

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

题目描述

https://darkbzoj.cc/problem/3569

简要题意：给定一张 $n$ 个 $m$ 条边的简单无向连通图，现在有 $q$ 次询问，每次询问给定若干条边，求将这些边的删掉后原图是否连通，询问之间独立，强制在线

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

Solution

注意到只有删边，我们考虑对原图建立一棵生成树，首先只有删掉这棵生成树上的边时才有可能导致原图不连通，那如果我们删掉树上的一条边 $(u,v)$ 使原图不连通，则说明所有能够连接 $u$ 和 $v$ 这两个连通块的非树边都被删掉了

那么相当于是每次删掉一个树边后判断是否该树边对应的非树边集合是否已经全部被删到，我们可以为每条非树边随机一个 $ull$ 范围内的整数，同时树边的值为它所对应的非树边的值的异或和，那么每次删边我们需要把边加入线性基，之后只需要判断线性基中是否出现 $0$ 即可

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
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#define maxn 100010
#define maxm 500010
#define ull unsigned long long
using namespace std;

struct LinearBasis {
    static const int n = 64;
    bool O; ull a[n + 1];

    void clear() { O = 0; for (int i = 0; i <= n; ++i) a[i] = 0; } 
    void insert(ull v) {
        for (int i = n; ~i; --i) {
            if (!(v >> i & 1)) continue;
            if (!a[i]) { a[i] = v; break; }
            v ^= a[i]; 
        }
        O |= !v; 
    }
} S;

int n, m, q; 

struct Edge {
    int u, v; ull w; 
} e[maxm]; bool vis[maxm];

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline bool merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return 0;
    return fa[x] = y, 1;
}

vector<pair<int, int>> G[maxn];
ull d[maxn];
void dfs(int u, int fa) {
    for (auto [v, k] : G[u]) {
        if (v == fa) continue;
        dfs(v, u); d[u] ^= d[v]; e[k].w = d[v];
    }
}

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

    cin >> n >> m;
    mt19937_64 gen(chrono::system_clock::now().time_since_epoch().count());
    uniform_int_distribution<ull> Rand(0, -1ull);
    for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v, e[i].w = Rand(gen);
    init_fa(n);
    for (int i = 1; i <= m; ++i) {
        int u = e[i].u, v = e[i].v; ull w = e[i].w;
        if (merge(u, v)) 
            G[u].emplace_back(v, i), G[v].emplace_back(u, i);
        else d[u] ^= w, d[v] ^= w;
    } dfs(1, 0); int cnt = 0; cin >> q; 
    for (int i = 1; i <= q; ++i) {
        int l, x; cin >> l; S.clear();
        while (l--) cin >> x, x ^= cnt, S.insert(e[x].w);
        cnt += !S.O; cout << (S.O ? "Disconnected" : "Connected") << "\n";
    }
    return 0;
}