[BZOJ4025]二分图 线段树对时间分治 并查集按秩合并


原题链接
给定一个图,每条边在一段时间内出现,问在每个时刻这张图是否是二分图.
使用线段树对时间分治,将每条边挂到对应区间的vector上,然后dfs整棵树即可.由于要求按照插入逆序拆边,需要用到并查集按秩合并.

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1002333
#define lson pos<<1
#define rson pos<<1|1
#define pb push_back
using namespace std;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
    x=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))x=x*10+c-'0',c=nc();
}
struct Node
{
    int x,y;
    Node(){}
    Node(int x0,int y0){x=x0,y=y0;}
};
int n,m,t;
vector<Node>e1[N<<2],e2[N<<2];
vector<int>v[N<<2];
int fa[N],rnk[N],dis[N];
inline void init()
{
    for(int i=1;i<=n;++i)fa[i]=i;
}
inline Node find(int x)
{
    Node re(x,0);
    while(re.x!=fa[re.x])re.y^=dis[re.x],re.x=fa[re.x];
    return re;
}
void insert(int pos,int l,int r,int x,int y,Node e)
{
    if(x<=l&&r<=y)
    {
        e1[pos].pb(e);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)insert(lson,l,mid,x,y,e);
    if(y>mid) insert(rson,mid+1,r,x,y,e);
}
void dfs(int pos,int l,int r,int flag)
{
    int i;
    Node e,tx,ty;
    for(i=0;flag&&i<e1[pos].size();++i)
    {
        e=e1[pos][i];
        tx=find(e.x),ty=find(e.y);
        if(tx.x!=ty.x)
        {
            if(rnk[tx.x]>rnk[ty.x])swap(tx,ty);
            fa[tx.x]=ty.x,dis[tx.x]=tx.y^ty.y^1;
            if(rnk[tx.x]==rnk[ty.x])rnk[ty.x]++,v[pos].pb(1);
            else v[pos].pb(0);
            e2[pos].pb(Node(tx.x,ty.x));
        }
        else if(tx.y==ty.y)flag=0;
    }
    if(l==r)
    {
        if(flag)puts("Yes");
        else puts("No");
    }
    else
    {
        int mid=(l+r)>>1;
        dfs(lson,l,mid,flag),dfs(rson,mid+1,r,flag);
    }
    for(i=0;i<e2[pos].size();++i)
    {
        e=e2[pos][i];
        fa[e.x]=e.x,dis[e.x]=0;
        if(v[pos][i])rnk[e.y]--;
    }
}
int main()
{
    read(n),read(m),read(t);
    init();
    Node e;
    int i,l,r;
    for(i=1;i<=m;++i)
    {
        read(e.x),read(e.y),read(l),read(r);
        l++;
        if(l<=r)insert(1,1,t,l,r,e);
    }
    dfs(1,1,t,1);
    return 0;
}
/*
5 6 7
1 2 0 7
2 3 0 3
3 1 2 7
4 5 3 6 
1 4 2 4
1 5 2 5

*/

发表评论

电子邮件地址不会被公开。 必填项已用*标注