「BZOJ 3569」DZY Loves Chinese II - 随机化 + 线性基

给一个无向连通图，每次指定其中的条边，求如果将这些边删除，剩余的图是否仍然连通。

链接

题解

任选一个点开始 DFS，可以得到图的一棵生成树。我们称一条非树边覆盖了树边，当且仅当与在树上的路径中包含和。

如果删除若干条边，使得原图不再连通，那么一定是删除了一条树边和所有覆盖了这条树边的非树边。我们给每条非树边赋一个随机权值，将每条树边的权值赋为所有覆盖它的非树边的权值的异或和 —— 如果删除的边的边权中，存在一个子集的异或和为零，则一定是选择了一条树边和所有覆盖它的非树边。使用线性基判断即可。

为每条树边赋权值的方式是，为每个点维护一个权值，对于每条非树边，将和的权值异或上这条边的权值，DFS 过程中将每个点的权值异或上所有子节点的权值（使异或上的权值从下向上传递，在处被消去），到的每个点的点权都被异或上了这条边的边权，将每条树边的边权赋为其靠近根的端点的点权即可。

代码

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>

const int MAXN = 100000;
const int MAXM = 500000;
const int MAXL = 40;     // for LinearBasis

struct Node {
    std::vector<struct Edge> e;
    bool vis;
    unsigned long long xorSum;
} N[MAXN + 1];

struct Edge {
    Node *s, *t;
    int id;

    Edge(Node *s, Node *t, int id) : s(s), t(t), id(id) {}
};

long long w[MAXM + 1];

inline void addEdge(int s, int t, int id) {
    N[s].e.push_back(Edge(&N[s], &N[t], id));
    N[t].e.push_back(Edge(&N[t], &N[s], id));
}

inline unsigned long long rand64() {
    return ((((unsigned long long)rand()) << 32) | ((unsigned long long)rand())) & ((1llu << 40) - 1);
}

inline void dfs1(Node *v, Node *fa) {
    v->vis = true;
    for (Edge *e = &v->e.front(); e && e <= &v->e.back(); e++) {
        if (e->t != fa) {
            if (!e->t->vis) {
                dfs1(e->t, v);
            } else if (!w[e->id]) {
                unsigned long long r = rand64();
                w[e->id] = r;

                v->xorSum ^= r;
                e->t->xorSum ^= r;
            }
        }
    }
}

inline void dfs2(Node *v, Node *fa) {
    v->vis = true;
    for (Edge *e = &v->e.front(); e && e <= &v->e.back(); e++) {
        if (e->t != fa) {
            if (!e->t->vis) {
                dfs2(e->t, v);
                w[e->id] = e->t->xorSum;
                v->xorSum ^= e->t->xorSum;
            }
        }
    }
}

struct LinearBasis {
    std::vector<unsigned long long> v;

    void build(unsigned long long *x, int n) {
        std::vector<unsigned long long> a(MAXL + 1);

        for (int i = 0; i < n; i++) {
            unsigned long long t = x[i];
            for (int j = MAXL; j >= 0; j--) {
                if (!(t & (1ull << j))) continue;

                if (a[j]) t ^= a[j];
                else {
                    for (int k = 0; k < j; k++) if (t & (1ull << k)) t ^= a[k];
                    for (int k = j + 1; k <= MAXL; k++) if (a[k] & (1ull << j)) a[k] ^= t;
                    a[j] = t;
                    break;
                }
            }
        }

        v.clear();
        for (int i = 0; i <= MAXL; i++) if (a[i]) v.push_back(a[i]);
    }
} lb;

inline bool solve(int *a, int k) {
    // for (int i = 0; i < k; i++) printf("%d%c", a[i], " \n"[i == k - 1]);
    // for (int i = 0; i < k; i++) printf("%llu%c", w[a[i]], " \n"[i == k - 1]);
#ifdef FORCE
    for (int s = 1; s < (1 << k); s++) {
        unsigned long long sum = 0;
        for (int i = 0; i < k; i++) if (s & (1 << i)) sum ^= w[a[i]];
        if (!sum) return false;
    }
    return true;
#else
    unsigned long long tmp[k];
    for (int i = 0; i < k; i++) tmp[i] = w[a[i]];
    lb.build(tmp, k);
    // printf("%lu <-> %d\n", lb.v.size(), k);
    return (int)lb.v.size() == k;
#endif
}

int main() {
    srand(20000528);

    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v, i);
    }

    dfs1(&N[1], NULL);
    for (int i = 1; i <= n; i++) N[i].vis = false;
    dfs2(&N[1], NULL);

    // for (int i = 1; i <= m; i++) printf("w[%d] = %llu\n", i, w[i]);

    int q;
    scanf("%d", &q);

    int ansSum = 0;
    while (q--) {
        int k;
        scanf("%d", &k);

        int a[k];
        for (int i = 0; i < k; i++) {
            scanf("%d", &a[i]);
            a[i] ^= ansSum;
        }

        bool ans = solve(a, k);
        ansSum += ans;

        puts(ans ? "Connected" : "Disconnected");
    }
}