洛谷P5787 二分图 /【模板】线段树分治/BZOJ4025 二分图 题解

洛谷P5787 二分图 /【模板】线段树分治/BZOJ4025 二分图题解

2020-02-03 xiaoh

题意

给定一张有\(n\)个节点的图(\(1\leq n \leq 10^5\))，初始情况下，图中没有任何边。接下来的\(k\)秒中(\(1\leq k \leq 10^5\))，总共会出现\(m\)条边(\(1\leq m \leq 2×10^5\))，第\(i\)条边在第\(l_i\)秒出现，第\(r_i\)秒消失。求每一秒这张图是否是二分图。

题解

既然是模板题，那么当然要使用线段树二分啦。线段树二分的思路，简单来讲就是先将整个问题离线下来，以时间轴为坐标建立一颗线段树，然后对于每一个修改，就在线段树上对应的位置打上永久的标记。接下来以dfs遍历整棵树并在通过标记时将其计入答案。通常可以解决一些容易解决区间加法，却不易解决区间减法的问题。在本题中，我们只要用一个扩展域并查集维护原图是否是二分图即可。注意由于在递归到叶子后要回溯操作，因此不能使用路径压缩，因此考虑按秩合并，并记录下具体修改的点即可。（吐槽一下数据有多水，我按秩合并修改时忘记还原了，结果依然非常完美的卡了过去）时间复杂度O(mlogk+mlogklogn)。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
    x=0;
    int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    x*=f;
    return;
}
template<typename T>
void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>=10) write(x/10);
    putchar(x%10+'0');
    return;
}
const int MAXN=100010,MAXM=200010;
int n,m,k;
int tot=1;
int edge[MAXM*2],w[MAXM*2],nxt[MAXM*2],hd[MAXN];//前向星
inline void add_edge(int u,int v)
{
    edge[tot]=v,w[tot]=u,nxt[tot]=hd[u],hd[u]=tot++;
}
struct node{//线段树
    int l,r;//左右区间
    vector<int> f;//永久标记，表示该时间区间的添加的边
}f[MAXN*4];
void build(int p,int l,int r)//递归建树
{
    f[p].l=l,f[p].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(p*2,l,mid),build(p*2+1,mid+1,r);
}
void modify(int p,int l,int r,int val)//区间修改，将边加入线段树中
{
    if(f[p].l>=l&&f[p].r<=r)
    {
        f[p].f.push_back(val);
        return;
    }
    int mid=(f[p].l+f[p].r)>>1;
    if(l<=mid) modify(p*2,l,r,val);
    if(r>mid) modify(p*2+1,l,r,val);
}
int a[MAXN*2],rk[MAXN*2];
inline void init()//初始化并查集
{
    for(int i=1;i<=2*n;i++) a[i]=i,rk[i]=1;
}
struct node2{//记录修改位置的结构体
    int a,b;
};
stack<node2> q;
int find(int x)//查询(不能使用路径压缩)
{
    return (x==a[x])? a[x]:find(a[x]);
}
int Union(int u,int v)//按秩合并
{
    u=find(u),v=find(v);
    if(find(u)==find(v)) return 0;
    if(rk[u]<=rk[v]) q.push({u,a[u]}),a[u]=v,rk[v]=max(rk[v],rk[u]+1);
    else q.push({v,a[v]}),a[v]=u,rk[u]=max(rk[u],rk[v]+1);
    return 1;
}
void back(int x)//注意此处写法有一些小问题，笔者忘记加上回溯秩rk的步骤了，但是依旧卡过了，请勿效仿
{
    for(int i=1;i<=x;i++) a[q.top().a]=q.top().b,q.pop();
}
void dfs(int p,bool ans)//递归整棵树求解答案
{
    int cnt=0;
    for(vector<int>::iterator it=f[p].f.begin();it!=f[p].f.end();it++)
    if(ans)
    {
        int x=edge[*it],y=w[*it];
        if(x==y)//若目前已经不是二分图了，那么所有的子节点也一定不是
        {
            ans=0;
            continue;
        }
        if(find(x)!=find(y)&&find(n+x)!=find(n+y)) cnt+=Union(x,n+y),cnt+=Union(y,n+x);
        else ans=0;
    }
    if(f[p].l==f[p].r)//递归边界
    {
        if(ans) printf("Yes\n");
        else printf("No\n");
        back(cnt);
        return;
    }
    dfs(p*2,ans),dfs(p*2+1,ans);
    back(cnt);
}
int main()
{
    read(n),read(m),read(k);
    build(1,1,k);
    for(int i=1;i<=m;i++)
    {
        int x,y,l,r;
        read(x),read(y),read(l),read(r);
        if(l>=r) continue;
        add_edge(x,y);
        modify(1,l+1,r,tot-1);
    }
    init();
    dfs(1,1);
    return 0;
}

洛谷P5787 二分图 /【模板】线段树分治/BZOJ4025 二分图 题解

原文：https://www.cnblogs.com/xiaoh105/p/12256652.html