A simple Blog for wyx I've been down the bottle hoping.
HDU5354 分治并查集 动态二分图 cdq分治
发表于: | 分类: Oi | 评论:0 | 阅读:156

给定一个无向图,问假如删除了一个点剩下的图是否是二分图
上面的那个询问是对于每个点的

首先如果每次都暴力的重新染色,你一定是$GG$的,于是你需要一些技♂巧

这个是典型的动态二分图,这类问题的处理方法有两种
1.对边进行询问,我们可以按时间分治,然后$Lct$维护最大生成树,如果一条边的加入使途中产生了奇环就会GG(自己画个图就知道了……)
2.对点进行询问,还是维护生成树是否有基环,但是这个时候用并查集维护点的联通情况,为了判断是否是奇环,常常采取$friend\quad and \quad enemy$并查集,说白了就是记录一下到代表元之间的距离的奇偶性就行了
但是注意并查集要支持恢复原来的版本,所以不能路径压缩只能按秩合并
回头看这个题,维护点的信息,那就直接分治并查集就行了……

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1e5+5;
const int M = N << 1;
using namespace std;

inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int n,m,cnt;
int fa[N];
int head[N];

struct graph
{
    int u,next,to;
    graph () {}
    graph (int _from,int _next,int _to)
    :u(_from),next(_next),to(_to){}
}edge[N<<1];

inline void add(int x,int y){
    edge[++cnt] = graph(x,head[x],y); head[x] = cnt;
    edge[++cnt] = graph(y,head[y],x); head[y] = cnt;
}
//data for pasttime
struct node
{
    int u,v,colu,colv,rku,rkv,fau,fav;
    node(){}
    node(int u,int v,int colu,int colv,int rku,int rkv,int fau,int fav):u(u),v(v),colu(colu),colv(colv),rku(rku),rkv(rkv),fau(fau),fav(fav){}
}stack[N];

int col[N],rk[N],top,ans[N];


void init(int n)
{
    cnt = top = 0;
    memset(head,false,sizeof head);
    for(int i=0;i<=n;i++) fa[i]=i,col[i]=rk[i]=1;
}

inline int find(int x){
    return fa[x] ^ x ? find(fa[x]) : fa[x];
}

int find_col(int x)
{
    if(fa[x]==x) return col[x];
    return !col[x] ? !find_col(fa[x]) : find_col(fa[x]);
}

bool merge(int u,int v)
{
    int a=find(u),b=find(v), x=find_col(u),y=find_col(v);
    int root,next;
    if(a==b) return x != y;
    if(rk[a]>rk[b]) root=a,next=b; else root=b,next=a;
    stack[top++]=node(a,b,col[a],col[b],rk[a],rk[b],fa[a],fa[b]);
    if(x==y && col[root]==1) col[next]^=1;
    fa[next]=root; rk[root]+=rk[next];
    return true;
}

bool Union(int l,int r,int a,int b) {
    bool flag=true;
    int u,v;
    for(int x=l;x<=r;x++)
        for(int i=head[x];i;i=edge[i].next) {
            u=edge[i].u;v=edge[i].to;
            if(a<=v && v<=b)  continue;
            if(!merge(u,v))
                flag=false;
        }
    return flag;
}

void back(int x) {
    node tmp;
    while(top>x) {
        tmp=stack[--top]; int u=tmp.u,v=tmp.v;
        rk[u]=tmp.rku,rk[v]=tmp.rkv, fa[u]=tmp.fau;fa[v]=tmp.fav, col[u]=tmp.colu;col[v]=tmp.colv;
    }
}

void solve(int l,int r,bool flag) {
    if(l==r) {
        ans[l]=flag;
        return;
    }
    int mid = (l+r) >> 1, pre = top;
    bool now=flag&Union(mid+1,r,l,mid);
    solve(l,mid,now); back(pre);
    now=flag&Union(l,mid,mid+1,r);
    solve(mid+1,r,now);
    back(pre);
}

int main(){// freopen("10.in","r",stdin);
    int T = read();
    while(T--)  {
        int n = read(), m = read(); init(n);
        for(int i=0;i<m;i++) add(read(),read());
        solve(1,n,true);
        for(int i=1;i<=n;i++) putchar(ans[i] ? '1' : '0');
        puts("");
    }
    return 0;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP