LOJ121 - [离线可过] 动态图连通性

2017/10/21

题目

这是一道被离线爆艹的模板题。

你要维护一张无向简单图。你被要求加入删除一条边及查询两个点是否连通。

0:加入一条边。保证它不存在。
1:删除一条边。保证它存在。
2:查询两个点是否联通。

点数 N ≤ 5000, 操作数 M ≤ 500000

解法 #1 LCT 维护最大时间生成树

对修改操作两两配对,即可得到形如 (u, v, l, r) 的四元组表示在 [l, r] 时间内有一条边 u - v

那么我们可以从小到大枚举时间 t ,每次插入所有四元组 (u, v, t, r) ,且最大化生成树树上路径的 min(r)

因此对于某时刻 t 两点 u, v 联通当且仅当该时刻 u - v 路径上的 min(r) >= t

复杂度

解法 #2 线段树分治 + 按秩合并并查集

用按秩合并并查集维护连通性,每次进入一个虚拟线段树节点就把所有覆盖整段的 tag 打上去,离开节点时撤销掉。

复杂度

代码

  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
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <cassert>
using namespace std;
typedef pair<int, int> pii;
const int SIZ = (500000 << 1) + 10007;

int N, M;

inline void sorted(int& u, int& v) {
    if(u > v) swap(u, v);
}

struct opt {
    int op, u, v, l, r;
};

int fa[SIZ], siz[SIZ];
int find(int x) {
    while(x ^ fa[x]) x = fa[x];
    return x;
}

struct stkt {
    int u, v, f, s;
} stk[SIZ]; int spos;

void unite(int u, int v) {
    if((u = find(u)) == (v = find(v))) return;

    if(siz[u] > siz[v]) swap(u, v);

    stk[spos++] = stkt{u, v, fa[u], siz[v]};
    fa[u] = v, siz[v] += siz[u] + (siz[u] == siz[v]);
}

void undo(const stkt &t) {
    fa[t.u] = t.f, siz[t.v] = t.s;
}

char ans[SIZ];
void solve(int L, int R, vector<opt*> w) {
    int pos = spos;
    for(opt* i : w)
        if(i->op && i->l <= L && R <= i->r) {
            unite(i->u, i->v);
        }

    if(L == R) for(opt* i : w)
        if(!i->op) ans[i->l] = (find(i->u) == find(i->v)) ? 'Y' : 'N';

    int Mid = (L + R) >> 1;
    // [L, Mid], [Mid+1, R]

    vector<opt*> ll, rr;
    for(opt *i : w) {
        if(i->op && i->l <= L && R <= i->r) continue;

        if(i->r <= Mid) ll.push_back(i);
        else if(Mid < i->l) rr.push_back(i);
        else ll.push_back(i), rr.push_back(i);
    }

    if(L < R) {
        if(!ll.empty()) solve(L, Mid, ll);
        if(!rr.empty()) solve(Mid+1, R, rr);
    }

    for(spos--;spos>=pos;spos--) {
        undo(stk[spos]);
    } spos++;

    assert(spos == pos);
}

map<pii, int> LUT;
vector<opt*> w;
int main() {
    scanf("%d %d", &N, &M);

    int op, u, v;
    for(int i=1;i<=M;i++) {
        scanf("%d %d %d", &op, &u, &v);
        sorted(u, v);

        if(op == 2) {
            w.push_back(new opt{0, u, v, i, i});
        } else {
            pii p(u, v);
            if(LUT.count(p)) {
                int L = LUT[p];
                int R = i;
                w.push_back(new opt{1, u, v, L, R});
                LUT.erase(p);
            } else {
                LUT[p] = i;
            }
        }
    }

    vector<pair<pii, int> > tmp(LUT.begin(), LUT.end());

    for(pair<pii, int> t : tmp) {
        w.push_back(new opt{1, t.first.first, t.first.second, t.second, M+1});
    }

    for(int i=1;i<=N;i++) fa[i] = i, siz[i] = 1;

    int L = 0, R = M+1; // [L, R]

    solve(L, R, w);

    for(int i=1;i<=M;i++) {
        if(ans[i]) { putchar(ans[i]); putchar('\n'); }
    }
}