I

II

分析

关于 I 的正确做法,戳这里

下面是一个比较正经的做法。

我们先随便搞一棵生成树出来,然后给非树边随机一个边权,再令树边的边权为所有覆盖它的非树边的边权的异或和。

那么如果整个图不连通了,则一定存在以下两种情况之一:

  • 存在一条树边,满足它和覆盖它的非树边都被断掉了。
  • 存在两条被相同的非树边集合覆盖的树边,满足这两条树边都被断掉了。

因此我们只需要查询断掉的边中是否存在一些数异或和为 $0$ 就好了。直接上线性基即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=500000+10;

int n,m,Q;

struct LinearBasis {
    int a[32];
    inline void clear() { memset(a,0,sizeof(a)); }
    inline void insert(int x) {
        for (re int i=31;~i;--i)
            if (x&(1<<i)) {
                if (!a[i]) { a[i]=x; break; }
                x^=a[i];
            }
    }
    inline int query(int x) {
        for (re int i=31;~i;--i)
            if (x&(1<<i)) {
                if (!a[i]) return 0;
                x^=a[i];
            }
        return 1;
    }
} B;

int f[N];
inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

struct edge { int v,nxt,id; } e[N<<1];
int head[N];
inline void addEdge(int u,int v,int id) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u],id},head[u]=cnt;
}

int w[M],val[N];
inline void dfs(int u,int fa) {
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u),w[e[i].id]^=val[v],val[u]^=val[v];
    }
}

int main() { srand(19491001); // 这里如果写某个八位质数是过不了的
    n=read(),m=read();
    for (re int i=1;i<=n;++i) f[i]=i;
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        if (find(u)==find(v)) w[i]=rand(),val[u]^=w[i],val[v]^=w[i];
        else addEdge(u,v,i),addEdge(v,u,i),f[find(u)]=find(v);
    }
    dfs(1,0);
    Q=read(); int lastans=0;
    while (Q--) { B.clear();
        int k=read(),flag=1;
        while (k--) {
            int x=read()^lastans;
            if (!B.query(w[x])) B.insert(w[x]);
            else flag=0;
        }
        puts(flag?"Connected":"Disconnected");
        lastans+=flag;
    }
    return 0;
}
最后修改:2019 年 10 月 31 日 10 : 09 AM