AHOI2013 解题报告

AHOI2013 D2T2 连通图

题目链接:Luogu P5227/BZOJ3237

题目限制

  • 时间限制:$2\texttt{s}$;
  • 空间限制:$256\texttt{MiB}$。

题目描述

给定一个无向连通图和若干个小集合,每个小集合包含一些边,对于每个集合,你需要确定将集合中的边删掉后改图是否保持联通。集合间的询问相互独立。

定义一个图为联通的当且仅当对于任意的两个顶点,都存在一条路径连接它们。

数据范围与提示

对于所有数据,有 $1\leq n,k\leq 10^5$,$1\leq m\leq 2\times 10^5$,$1\leq c\leq 4$。

题解

显然可以用线段树分治来维护边的出现时间,我们不妨用可撤销并查集来维护图的连通性,需要用按秩合并来保证复杂度。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
    reg char ch = getchar();
    reg int res = 0;
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
        res = 10 * res + (ch ^ '0'), ch = getchar();
    return res;
}

const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
const int MAXK = 1e5 + 5;

struct Edge
{
    int u, v;
};

int n, m, k;
Edge E[MAXM];
vector<int> V[MAXM];

namespace SegmentTree
{
#define lson ((k) << 1)
#define rson ((k) << 1 | 1)
#define mid (((l) + (r)) >> 1)
    struct Node
    {
        vector<int> V;
#define V(x) unit[(x)].V
    };
    Node unit[MAXK << 2];
    inline void update(reg int k, reg int l, reg int r, reg int L, reg int R, const int &id)
    {
        if (L <= l && r <= R)
        {
            V(k).push_back(id);
            return;
        }
        if (L <= mid && mid < R)
            update(lson, l, mid, L, R, id), update(rson, mid + 1, r, L, R, id);
        else if (L <= mid)
            update(lson, l, mid, L, R, id);
        else
            update(rson, mid + 1, r, L, R, id);
        return;
    }
    namespace UnionFind
    {
        int fa[MAXN], siz[MAXN], dep[MAXN];
        inline void Init(reg int n)
        {
            for (reg int i = 1; i <= n; ++i)
                fa[i] = i, siz[i] = dep[i] = 1;
            return;
        }
        inline int find(reg int x)
        {
            while (x != fa[x])
                x = fa[x];
            return x;
        }
    } // namespace UnionFind
    struct Chunk
    {
        int rb, f, siz;
        inline Chunk(reg int rb = 0, reg int f = 0, reg int siz = 0) : rb(rb), f(f), siz(siz)
        {
            return;
        }
    };
    int top;
    Chunk S[MAXM];
    inline void Do(reg int id, reg bool &flag)
    {
        using namespace UnionFind;
        int ra = find(E[id].u), rb = find(E[id].v);
        if (ra == rb)
            return;
        if (dep[ra] < dep[rb])
            swap(ra, rb);
        S[++top] = Chunk(rb, dep[ra] == dep[rb], siz[rb]);
        fa[rb] = ra, dep[ra] += (dep[ra] == dep[rb]), siz[ra] += siz[rb];
        if (siz[ra] == n)
            flag = true;
        return;
    }
    inline void unDo(const Chunk &x)
    {
        using namespace UnionFind;
        reg int &rb = fa[x.rb];
        dep[rb] -= x.f, siz[rb] -= x.siz, rb = x.rb;
        return;
    }
    inline void print(reg int k, reg int l, reg int r, bool flag)
    {
        reg int tmp = top;
        for (vector<int>::iterator it = V(k).begin(); it != V(k).end(); ++it)
            Do(*it, flag);
        if (l == r)
            puts(flag ? "Connected" : "Disconnected");
        else
            print(lson, l, mid, flag), print(rson, mid + 1, r, flag);
        while (top != tmp)
            unDo(S[top--]);
        return;
    }
    inline void Solve(void)
    {
        UnionFind::Init(n);
        print(1, 1, k, false);
        return;
    }
#undef lson
#undef rson
#undef mid
} // namespace SegmentTree

int main(void)
{
    n = read(), m = read();
    for (reg int i = 1; i <= m; ++i)
        E[i].u = read(), E[i].v = read();
    k = read();
    for (reg int i = 1; i <= m; ++i)
        V[i].push_back(0);
    for (int i = 1; i <= k; ++i)
        for (reg int c = read(); c; --c)
            V[read()].push_back(i);
    for (reg int i = 1; i <= m; ++i)
        V[i].push_back(k + 1);
    for (int i = 1; i <= m; ++i)
        for (reg int j = 1, siz = V[i].size(); j < siz; ++j)
            if (V[i][j - 1] + 1 <= V[i][j] - 1)
                SegmentTree::update(1, 1, k, V[i][j - 1] + 1, V[i][j] - 1, i);
    SegmentTree::Solve();
    return 0;
}

当然,也可以用 LCT 解决,代码如下:

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <tuple>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define inl inline
#define re register int
#define fa(x) t[x].fa
#define ls(x) t[x].child[0]
#define rs(x) t[x].child[1]
#define ll long long
const int inf = 0x7fffffff;
#define lowbit(x) ((x) & (-x))
using namespace std;
#ifndef _DEBUG
#define getchar() (*(IOB.in.p++))
#define putchar(c) (*(IOB.out.p++) = (c))
#define io_eof() (IOB.in.p >= IOB.in.pend)
struct IOBUF
{
    struct
    {
        char buff[1 << 26], *p, *pend;
    } in;
    struct
    {
        char buff[1 << 26], *p;
    } out;
    IOBUF()
    {
        in.p = in.buff;
        out.p = out.buff;
        in.pend = in.buff + fread(in.buff, 1, 1 << 26, stdin);
    }
    ~IOBUF() { fwrite(out.buff, 1, out.p - out.buff, stdout); }
} IOB;
#endif
template <typename IO>
inl void write(IO x)
{
    if (x == 0)
        return (void)putchar('0');
    if (x < 0)
        putchar('-'), x = -x;
    static char buf[30];
    char *p = buf;
    while (x)
    {
        *(p++) = x % 10 + '0';
        x /= 10;
    }
    while (p > buf)
        putchar(*(--p));
}
inl void writestr(const char *s)
{
    while (*s != 0)
        putchar(*(s++));
}
template <typename IO>
inl void writeln(IO x) { write(x), putchar('\n'); }
template <typename IO>
inl void writesp(IO x) { write(x), putchar(' '); }
inl int readstr(char *s)
{
    char *begin = s, c;
    while (1)
    {
        c = getchar();
        if (c < 33 || c > 127)
            break;
        *(s++) = c;
    }
    *s = 0;
    return s - begin;
}
template <typename IO>
inl IO read()
{
    IO x = 0;
    register bool w = 0;
    register char c = getchar();
    while (c > '9' || c < '0')
    {
        if (c == '-')
            w = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return w ? -x : x;
}
int n, m;
struct node
{
    int w, min, size, fa, child[2], vir;
    bool filp;
} t[10000001];
inl void maintain(int x)
{
    t[x].size = t[ls(x)].size + t[rs(x)].size + t[x].vir + (x <= n);
    if (x > n)
        t[x].min = x;
    if (t[x].w >= t[t[ls(x)].min].w)
        t[x].min = t[ls(x)].min;
    if (t[t[x].min].w >= t[t[rs(x)].min].w)
        t[x].min = t[rs(x)].min;
} //vir是虚子树的size和
inl bool poi(int x)
{
    return rs(fa(x)) == x;
}
inl bool nroot(int x)
{
    return ls(fa(x)) == x || rs(fa(x)) == x;
}
inl void rotate(int x)
{
    re f = fa(x), gf = fa(f), fs = poi(x), gfs = poi(f), s = t[x].child[fs ^ 1];
    if (nroot(f))
        t[gf].child[gfs] = x;
    t[f].child[fs] = s, t[x].child[fs ^ 1] = f;
    if (s)
        fa(s) = f;
    fa(x) = gf, fa(f) = x;
    maintain(f);
}
inl void reverse(int x)
{
    swap(ls(x), rs(x)), t[x].filp ^= 1;
}
inl void pushdown(int x)
{
    if (t[x].filp)
    {
        if (ls(x))
            reverse(ls(x));
        if (rs(x))
            reverse(rs(x));
        t[x].filp = 0;
    }
}
inl void push(int x)
{
    if (nroot(x))
        push(fa(x));
    pushdown(x);
}
inl void splay(int x)
{
    push(x);
    while (nroot(x))
    {
        if (nroot(fa(x)))
            poi(x) == poi(fa(x)) ? rotate(fa(x)) : rotate(x);
        rotate(x);
    }
    maintain(x);
}
inl void access(int x)
{
    for (re i = 0; x; x = fa(i = x))
    {
        splay(x), t[x].vir += t[rs(x)].size, t[x].vir -= t[rs(x) = i].size, maintain(x);
    }
}
inl void makeroot(int x)
{
    access(x), splay(x), reverse(x);
}
inl void split(int x, int y)
{
    makeroot(y), access(x), splay(x);
}
inl void link(int x, int y)
{
    split(x, y), fa(y) = x, t[x].vir += t[y].size, maintain(x);
}
inl void cut(int x, int y)
{
    split(x, y);
    fa(y) = ls(x) = 0, maintain(x);
}
inl int findroot(int x)
{
    access(x), splay(x), pushdown(x);
    while (ls(x))
        pushdown(x = ls(x));
    splay(x);
    return x;
}
inl bool query()
{
    access(1), splay(1);
    return t[1].size == n;
}
struct edge
{
    int u, v, w;
} e[10000001];
struct quiz
{
    bool op, flag;
    int i, tim;
} q[10000001];
int now[10000001], num, ans[10000001], st[1000001], top;
signed main()
{
    n = read<int>(), m = read<int>();
    for (re i = 0; i <= n; i++)
        t[i].w = inf;
    for (re i = 1; i <= m; i++)
    {
        re x = read<int>(), y = read<int>();
        e[i] = edge{x, y}, now[i] = i;
        q[++num] = quiz{1, 0, i, 0};
    } //op为0表示删除(cut),为1表示加入(link),flag表示是否为询问
    re k = read<int>(), a, tot = m;
    for (re i = 1; i <= k; i++)
    {
        a = read<int>();
        for (re j = 1; j <= a; j++)
        {
            re x = read<int>();
            e[now[x]].w = i - 1;
            t[now[x] + n].w = i - 1;
            q[++num] = quiz{0, 0, now[x], i};
            e[++tot].u = e[now[x]].u, e[tot].v = e[now[x]].v, now[x] = tot;
            st[++top] = now[x];
        }
        q[++num].flag = 1;
        if (i != k)
        {
            while (top)
            {
                q[++num] = quiz{1, 0, st[top--], i};
            }
        }
    }
    for (re i = 1; i <= m; i++)
    {
        if (!e[now[i]].w)
        {
            e[now[i]].w = k;
            t[now[i] + n].w = k;
        }
    }
    tot += n;
    for (re i = 1; i <= tot; i++)
    {
        t[i].size = 1;
    } //初始化
    for (re i = 1; i <= num; i++)
    { //维护最大生成树
        if (q[i].flag)
        {
            writestr(query() ? "Connected\n" : "Disconnected\n");
        }
        else
        {
            re j = q[i].i, u = e[j].u, v = e[j].v, w = e[j].w;
            makeroot(u);
            if (q[i].op)
            {
                if (findroot(v) == u)
                {
                    re minn = t[u].min;
                    if (t[minn].w >= w)
                        continue;
                    cut(e[minn - n].u, minn), cut(e[minn - n].v, minn);
                }
                link(u, j + n), link(v, j + n);
            }
            else
            {
                if (findroot(v) == u)
                {
                    maintain(j + n);
                    if (!t[j + n].fa && !t[j + n].size)
                        continue;
                    cut(e[j].u, j + n), cut(e[j].v, j + n);
                }
            }
        }
    }
}
Pages: 1 2 3 4 5 6 7 8