求卡常 / 证伪
查看原帖
求卡常 / 证伪
1013955
1234567890sjx楼主2024/8/26 17:38
#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <random>
#include <queue>
#define int long long
const int N = 1000100;
std::vector<std::pair<int, int>> z[N];
struct qwq {
    int u, v, w;
} edge[N];
int fa[N], idval[N], deg[N], Xor[N], vv[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
signed main() {
    int n, m;
    scanf("%lld%lld", &n, &m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%lld%lld", &u, &v);
        edge[i] = {u, v, 0};
    }
    std::uniform_int_distribution<int> mt(1, 100100100100100100);
    std::mt19937_64 rd;
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
    for (int i = 1; i <= m; ++i)
        if (find(edge[i - 1].u) != find(edge[i - 1].v)) {
            fa[find(edge[i - 1].u)] = find(edge[i - 1].v);
            z[edge[i - 1].u].emplace_back(edge[i - 1].v, i - 1);
            z[edge[i - 1].v].emplace_back(edge[i - 1].u, i - 1);
            ++deg[edge[i - 1].u], ++deg[edge[i - 1].v];
        } else idval[i - 1] = mt(rd);
    for (int i = 0; i < m; ++i)
        if (idval[i]) Xor[edge[i].u] ^= idval[i], Xor[edge[i].v] ^= idval[i];
    std::queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (deg[i] == 1 && i != 1) q.push(i), vv[i] = 1;
    if (q.size()) {
        while (q.size()) {
            int f = q.front();
            q.pop();
            for (auto &[g, w] : z[f]) if (!vv[g]) {
                Xor[g] ^= Xor[f];
                idval[w] = Xor[f];
                if ((g != 1 && --deg[g] == 1) || (g == 1 && !--deg[g])) {
                    q.push(g);
                    vv[g] = 1;
                }
            }
        }
    }
    int qx;
    scanf("%lld", &qx);
    int qwa = 0;
    while (qx--) {
        int ox;
        scanf("%lld", &ox);
        ox ^= qwa;
        std::vector<int> lz;
        for (int i = 0; i < ox; ++i) {
            int p;
            scanf("%lld", &p);
            p ^= qwa;
            --p;
            lz.emplace_back(p);
        }
        int ok = 1;
        for (int i = 1; i < (1 << ox); ++i) {
            int sx = 0;
            for (int j = 0; j < ox; ++j)
                if (i >> j & 1)
                    sx ^= idval[lz[j]];
            if (!sx) {
                ok = 0;
                break;
            }
        }
        puts(ok ? "Connected" : "Disconnected");
        if (ok)
            ++qwa;
    }
}
2024/8/26 17:38
加载中...