Codeforces ECR #022 : F. Bipartite Checking

こちらも勉強になった。
http://codeforces.com/contest/813/problem/F

問題

N頂点からなるグラフがある。
初期状態で辺はない。

ここに辺の追加削除を行うクエリが与えられる。
各クエリを順次処理した直後、グラフは二部グラフであるかどうかを答えよ。

解法

二部グラフの判定法として、頂点を二倍化する方法がある。
ただし辺の削除があるので一般的なUnion-Findデータ構造は使えない。

Union-Findは一般的にfind時に辺の集約を行うが、これを行わないようにするものを考えよう。
するとunite時に書き換える変数の数はたかが知れているので、書き換え前の値を覚えておくことで追加の逆順に巻き戻しが可能となる。
unite時に木の高さが増えないように連結していけば、findのコストもO(α(|V|))は無理だがO(log(|V|))で抑えることができる。

先にクエリを全部読み、各辺eが存在しているクエリの区間[L,R]の集合を求める。
その後、SegTreeを親から子に辿る要領でDFSしよう。
その際、今見ている区間をすべて覆う辺の区間があればその時点でuniteする。

そして二部グラフが崩れることが判定できれば、その区間全体は二部グラフでない。
二部グラフのままである場合、DFSで両子ノードを探索する。
その際、クエリは対応する区間のものだけ子ノードに処理される。
DFSの後処理を抜ける際にuniteした分を巻き戻していけば、1個のUnion-Find構造を使いまわして各区間の二部グラフ判定ができる。

int N,Q;
vector<vector<int>> V;
map<pair<int,int>,int> M;
int ret[101010];

template<int um> class UF_pop {
	public:
	vector<int> par,rank; vector<vector<int>> hist;
	UF_pop() {par=rank=vector<int>(um,0); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):operator[](par[x]);}
	void pop() {
		if(hist.size()) {
			auto a=hist.back();
			hist.pop_back();
			par[a[0]]=a[1]; rank[a[0]]=a[2];
			par[a[3]]=a[4]; rank[a[3]]=a[5];
		}
	}
	void operator()(int x,int y) {
		x=operator[](x); y=operator[](y);
		hist.push_back({x,par[x],rank[x],y,par[y],rank[y]});
		if(x==y) return;
		if(rank[x]<rank[y]) par[x]=y;
		else rank[x]+=(rank[x]==rank[y]), par[y]=x;
	}
};

void dfs(int L,int R,UF_pop<201010>& uf,vector<vector<int>> V) {
	vector<vector<int>> LV,RV;
	int nums=0;
	int M=(L+R)/2;
	int con=0;
	
	if(V.empty()) return;
	
	FORR(v,V) {
		if(v[2]<=L && R<=v[3]) {
			uf(v[0]*2,v[1]*2+1);
			uf(v[0]*2+1,v[1]*2);
			if(uf[v[0]*2]==uf[v[0]*2+1]) con=1;
			if(uf[v[1]*2]==uf[v[1]*2+1]) con=1;
			nums+=2;
		}
		else {
			if(v[2]<M) LV.push_back({v[0],v[1],max(L,v[2]),min(M,v[3])});
			if(v[3]>M) RV.push_back({v[0],v[1],max(M,v[2]),min(R,v[3])});
		}
	}
	
	int i;
	if(con) {
		for(int i=L;i<R;i++) ret[i]=1;
	}
	else {
		dfs(L,M,uf,LV);
		dfs(M,R,uf,RV);
	}
	while(nums--) uf.pop();
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,Q) {
		cin>>x>>y;
		x--,y--;
		if(x>y) swap(x,y);
		
		if(M.count({x,y})==0) {
			M[{x,y}]=i;
		}
		else {
			V.push_back({x,y,M[{x,y}],i});
			M.erase({x,y});
		}
	}
	FORR(r,M) V.push_back({r.first.first,r.first.second,r.second,Q});
	
	UF_pop<201010> uf;
	dfs(0,Q,uf,V);
	
	FOR(i,Q) {
		if(ret[i]) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
}

まとめ

巻き戻し可能なUnion-Find初めて知った。
Eと合わせて確かに教育的な回だった。