P5787 并查集判断二分图

· · 个人记录

前言

其实并不是什么值得写题解的东西，只是证明自己还没有似，所以来氵一篇题解。

思路

并查集怎么判断二分图呢？

首先考虑其他判断二分图的方法（搜索染色），染色看起来不是很好用并查集维护（毕竟不是合并染色），于是考虑其他思路。

首先考虑并查集到底要维护什么，由于二分图可以划分为两个集合，而集合正是并查集擅长维护的东西，于是我们的并查集维护的内容就表示「在并查集中为一个集合的元素，在二分集合中属于同一个集合」。

二分图的突破点一般在于它的一些性质。考虑基本定义，可以发现和一个点直接相连的所有点在一个集合内，我们对「与一个点相连的点」建立一个虚拟集合，而这个虚拟集合内的所有元素自然属于同一个二分集合。每当我们要在 u,v 之间连边的时候，我们就合并 u 和 “v 的虚拟集合”以及 v 和 “u 的虚拟集合”，也就是说和 v 的虚拟集合里的元素都和 u 在同一个二分集合中（容易得到）。

当一个元素 u 在自己的虚拟集合的时候，就说明它同时处于两个集合，发生矛盾，于是就不是二分图了，反之则是二分图。

解题

如果要做 P5787，我们需要在以上思路的基础上用线段树分治和可撤销并查集来维护时间轴。

代码

#include<bits/stdc++.h>
#define Akano 1
#define pure__Elysia 0
#define loves ^
using namespace std;
constexpr int MAXN = 2e5 + 1018 + 1108;
//可撤销的启发式合并并查集
template<int SIZE>
class DSU{
private:
    int fa[SIZE],size[SIZE];
    vector<pair<int,int> > history;
    int Find(int x){
        if(fa[x] == x)return x;
        return Find(fa[x]);
    }
public:
    inline bool Merge(int u,int v){
        u = Find(u),v = Find(v);
        if(u == v)return false;
        if(size[u] < size[v])swap(u,v);//size_u >= size_v
        fa[v] = u,size[u] += size[v];
        history.emplace_back(u,v);
        return true;
    }
    inline bool Together(int u,int v){
        return Find(u) == Find(v);
    }
    inline bool Undo(){
        if(history.empty())return false;
        const int u = history.back().first,v = history.back().second;
        history.pop_back();
        fa[v] = v,size[u] -= size[v];
        return true;
    }
    inline void Init(int x){
        for(int i = 1;i <= x;i++){
            fa[i] = i,size[i] = 1;
        }
        return ;
    }
};
DSU<MAXN> dsu;
int n,m,k;
class SegmentTree{
private:
    vector<pair<int,int> > segs[MAXN * 4];
    void Insert(int p,int l,int r,int OBJL,int OBJR,pair<int,int> pr){
        if(OBJL <= l && r <= OBJR){
            segs[p].push_back(pr);
            return ;
        }
        const int mid = (l + r) >> 1;
        if(mid >= OBJL)Insert(p*2,l,mid,OBJL,OBJR,pr);
        if(mid < OBJR)Insert(p*2+1,mid+1,r,OBJL,OBJR,pr);
        return ;
    }
    void Execute(int p,int l,int r,bool ans){
        int tot = 0;
        for(auto seg : segs[p]){
            const int u = seg.first,v = seg.second,uNear = u + n,vNear = v + n;
            tot += dsu.Merge(uNear,v),tot += dsu.Merge(vNear,u);
            if(dsu.Together(u,uNear) || dsu.Together(v,vNear)){
                ans = false;
            }
        }
        if(l == r){
            if(ans == true){
                cout<<"Yes\n";
            }else{
                cout<<"No\n";
            }
        }else{
            const int mid = (l + r) >> 1;
            Execute(p*2,l,mid,ans),Execute(p*2+1,mid+1,r,ans);
        }
        for(int i = 1;i <= tot;i++){
            dsu.Undo();
        }
        return ;
    }
public:
    inline void Insert(int l,int r,pair<int,int> pr){
        return Insert(1,1,n,l,r,pr);
    }
    inline void Execute(){
        return Execute(1,1,n,true);
    }
}tr;
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    dsu.Init(2*n);
    for(int i = 1,u,v,l,r;i <= m;i++){
        cin>>u>>v>>l>>r;
        tr.Insert(l+1,r,{u,v});
    }
    tr.Execute();
    return not(Akano loves pure__Elysia);
}