【BZOJ 4025】二分圖

傳送門

problem

出一個 n n n 個節點的圖，有 m m m 條邊，每條邊會在 s i s_i si​ 時刻出現，在 t i t_i ti​ 消失。對于 ∀ i ∈ [ 1 , T ] \forall i\in[1,T] ∀i∈[1,T]，請查詢在 i i i 時刻圖是否為二分圖。

資料範圍： n , T ≤ 1 0 5 n,T\le10^5 n,T≤105， m ≤ 2 × 1 0 5 m\le2\times 10^5 m≤2×105， 0 ≤ s i ≤ t i ≤ T 0\le s_i\le t_i\le T 0≤si​≤ti​≤T。

solution

這是一道線段樹分治的闆子題。

首先有一個結論，即一個圖是二分圖的充要條件是不含奇環。

因為有删邊操作，我們用線段樹分治，現在的任務就是如何判奇環。

加邊時，若 ( u , v ) (u,v) (u,v) 不連通，那麼不會構成環，把它加進來。

若 ( u , v ) (u,v) (u,v) 已經聯通，則查詢 u u u 和 v v v 兩點的距離。若為偶數則加上這條邊後會形成奇環，那麼圖之後都不可能是二分圖，直接判掉即可。若為奇數則可以直接忽略這條邊，因為如果将來某條邊會與這條邊形成奇環，則用之前 u u u 到 v v v 之間的路徑（長度為奇數）替代這條邊（長度為 1 1 1）同樣也會形成奇環。

由于我們隻需要維護奇偶性，可以直接用異或操作。

時間複雜度 O ( n log ⁡ 2 n ) O(n\log^2n) O(nlog2n)。

code

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
typedef pair<int,int> Pair;
int n,m,T;
int fa[N],ans[N],Rank[N],val[N];
struct node{
	Pair del;bool flag;
	node(Pair _del,bool _flag):del(_del),flag(_flag){}
};
vector<Pair>e[N<<2];
vector<node>op[N<<2];
void Modify(int root,int l,int r,int x,int y,int u,int v){
	if(l>=x&&r<=y){
		return e[root].push_back(make_pair(u,v));
	}
	int mid=(l+r)>>1;
	if(x<=mid)  Modify(root<<1,l,mid,x,y,u,v);
	if(y>mid)  Modify(root<<1|1,mid+1,r,x,y,u,v);
}
int find(int &x){
	int now=0;
	while(x!=fa[x])  now^=val[x],x=fa[x];
	return now;
}
void Query(int root,int l,int r){
	bool flag=true,now;
	for(int i=0;i<e[root].size();++i){
		int x=e[root][i].first,y=e[root][i].second,u=find(x),v=find(y);
		if(x==y){
			if(!(u^v)){
				flag=false;
				for(int i=l;i<=r;++i)  ans[i]=0;
				break;
			}
			continue;
		}
		if(Rank[x]<Rank[y])  swap(x,y);
		fa[y]=x,val[y]=u^v^1,now=0;
		if(Rank[x]==Rank[y])  ++Rank[x],now=1;
		op[root].push_back(node(make_pair(x,y),now));
	}
	int mid=(l+r)>>1;
	if(l!=r&&flag)  Query(root<<1,l,mid),Query(root<<1|1,mid+1,r);
	for(int i=op[root].size()-1;~i;--i){
		int x=op[root][i].del.first,y=op[root][i].del.second;
		fa[y]=y,val[y]=0,Rank[x]-=op[root][i].flag;
	}
}
int main(){
	int u,v,l,r;
	scanf("%d%d%d",&n,&m,&T);
	for(int i=1;i<=n;++i)  fa[i]=i,ans[i]=Rank[i]=1;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&u,&v,&l,&r);
		if(l<r)  Modify(1,1,T,l+1,r,u,v);
	}
	Query(1,1,T);
	for(int i=1;i<=T;++i)  puts(ans[i]?"Yes":"No");
	return 0;
}