Description

神校 XJ 之学霸兮, Dzy 皇考曰 JC.

摄提贞于孟陬兮, 惟庚寅 Dzy 以降.

纷 Dzy 既有此内美兮, 又重之以修能.

遂降临于 OI 界, 欲以神力而凌♂辱众生.

今 Dzy 有一魞歄图, 其上有 \(n\) 座祭坛, 又有 \(m\) 条膴蠁边.

时而 Dzy 狂 WA 而怒发冲冠, 神力外溢, 遂有 \(k\) 条膴蠁边灰飞烟灭.

而后俟其日 A50 题则又令其复原. (可视为立即复原)

然若有祭坛无法相互到达, Dzy 之神力便会大减, 于是欲知其是否连通.

Input

第一行 \(n, m\)

接下来 \(m\) 行 \(x, y\): 表示 \(m\) 条膴蠁边, 依次编号

接下来一行 \(Q\)

接下来 \(Q\) 行:

每行第一个数 \(k\) 而后 \(k\) 个编号 \(c_1 \sim c_k\): 表示 \(k\) 条边, 编号为 \(c_1 \sim c_k\)

为了体现在线,\(c_1 \sim c_k\) 均需异或之前回答为连通的个数

Output

对于每个询问输出: 连通则为 “Connected”, 不连通则为 “Disconnected” (不加引号).

Sample Input

5 10
2 1
3 2
4 2
5 1
5 3
4 1
4 3
5 2
3 1
5 4
5
1 1
3 7 0 3
4 0 7 4 6
2 2 7
4 5 0 2 13

Sample Output

Connected
Connected
Connected
Connected
Disconnected

Data Range

对于所有数据, 满足:\(n \leq 10^5, m \leq 5 \times 10^5, Q \leq 50000, 1 \leq k \leq 15\), 并且: 数据保证没有重边与自环.

Explanation

题目大意:\(n\) 个点,\(m\) 条边,\(k\) 次询问, 每次询问去掉某条边之后图是否连通.

我们找到这个图的任意一棵生成树, 然后对于每条非树边将其的权值赋为一个随机数.

对于每条树边, 我们将这条树边的权值设为所有覆盖这条树边的边权的异或和.

那么图不连通当且仅当删除一条树边和覆盖这条树边的所有边集, 而由于刚才的处理一条树边和覆盖这条边的所有边集的异或和为零.

于是问题转化成了对于给定的 \(k\) 条边是否存在一个边权的异或和为零的子集果断高斯消元由于使用了随机化所以碰撞率极低.

参照这篇题解:http://blog.csdn.net/PoPoQQQ/article/details/41865807

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 500100, maxm = 500100;

class IDontKnowWhatThisDoes
{
public:
    struct edge
    {
        int u, v, rnd;
        edge *next;
    };
    int n, root, ecnt;
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    bool vis[maxn];
    int b[maxn];
    void dfs1(int p)
    {
        vis[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (!vis[ep->v]) {
                dfs1(ep->v);
            } else {
                ep->rnd = rand();
                b[p] ^= ep->rnd;
                b[ep->v] ^= ep->rnd;
            }
        return ;
    }
    void dfs2(int p)
    {
        vis[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (!vis[ep->v]) {
                dfs2(ep->v);
                ep->rnd ^= b[ep->v];
                b[p] ^= b[ep->v];
            }
        return ;
    }
    void construct(void)
    {
        root = 1;
        memset(vis, 0, sizeof(vis));
        dfs1(root);
        memset(vis, 0, sizeof(vis));
        dfs2(root);
        return ;
    }
    // Here goes the checking
    int c[64];
    bool judge(int k)
    {
        int now = 0;
        for (int i = 1 << 30; i; i >>= 1) {
            int j = now + 1;
            for (; j <= k; j++)
                if (c[j] & i)
                    break;
            if (j == k + 1)
                continue;
            swap(c[j], c[++now]);
            for (int j = 1; j <= k; j++)
                if (j != now && c[j] & i)
                    c[j] ^= c[now];
        }
        if (c[k])
            return false;
        return true;
    }
} graph;

int n, m, T;

int main(int argc, char** argv)
{
    srand(19990610);
    scanf("%d%d", &n, &m);
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        if (a > b) swap(a, b);
        graph.add_edge(a, b);
    }
    scanf("%d", &T);
    graph.construct();
    int res = 0;
    for (int idx = 1, k; idx <= T; idx++) {
        scanf("%d", &k);
        for (int i = 1, x; i <= k; i++) {
            scanf("%d", &x);
            x ^= res;
            graph.c[i] = graph.epool[x].rnd;
        }
        if (graph.judge(k)) {
            printf("Disconnected\n");
        } else {
            res += 1;
            printf("Connected\n");
        }
    }
    return 0;
}