bzoj3569

线性基

非常高端

强制在线动态图

我们先搞出一个dfs树，然后所有非树边都和树边形成一个环。我们考虑什么情况会不连通，当且仅当树边和dfs序大于当前点的返祖边都被断掉才不连通，那么我们给每个非树边赋一个权值，树边的权值就是所有这些返祖边的权值的异或和，这样一遍dfs就行了。

然后就是怎么判断，因为树边的权值等于有关非树边的异或和，那么就是当前给的边集有一个自己异或和等于0，这个可以用线性基来判断。

然后，我又在读入的时候break了，noipday1t2就因为这个调了半个小时。。。。。。

#include<bits/stdc++.h>

using namespace std;

const int N = 5e5 + ;

inline int rd()

{

    int x = , f = ; char c = getchar();

    while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

    while(c >= '' && c <= '') { x = x *  + c - ''; c = getchar(); }

    return x * f;

}

struct edge {

    int nxt, to, w, id;

} e[N << ];

int n, m, cnt = , Q, ans;

int head[N], c[N], w[N], vis[N], d[N], v[];

void link(int u, int v, int id)

{

    e[++cnt].nxt = head[u];

    head[u] = cnt;

    e[cnt].to = v;

    e[cnt].id = id;

}

void dfs(int u, int last)

{

    vis[u] = ;

    for(int i = head[u]; i; i = e[i].nxt) if(e[i].to != last)

    {

        if(vis[e[i].to])

        {

            if(!w[e[i].id])

            {

                int t = rand();

                w[e[i].id] = t;

                d[u] ^= t;

                d[e[i].to] ^= t;

            }

        }

        else

        {

            dfs(e[i].to, u);

            w[e[i].id] = d[e[i].to];

            d[u] ^= d[e[i].to];

        }

    }

}

bool check(int x)

{

    for(int i = ; i >= ; --i) if(x & ( << i))

    {

        if(!v[i])

        {

            v[i] = x;

            return ;

        }

        else x ^= v[i];

    }

    return x;

}

int main()

{

    srand();

    n = rd();

    m = rd();

    for(int i = ; i <= m; ++i)

    {

        int u = rd(), v = rd();

        link(u, v, i);

        link(v, u, i);

    }

    dfs(, );

    Q = rd();

    while(Q--)

    {

        int k = rd(), f = ;

        memset(v, , sizeof(v));

        for(int i = ; i <= k; ++i)

        {

            c[i] = w[rd() ^ ans];

            if(!check(c[i])) f = ;

        }

        puts(f ? "Connected" : "Disconnected");

        ans += f;

    }

    return ;

}

巴特西

bzoj3569

最新文章

热门文章