Croc Champ 2013 - Round 1 : D. Connected Components

さてD。だんだん難しくなってきた。
http://codeforces.com/contest/292/problem/D

問題

N個の点とM個の辺からなるグラフが与えられる。
そこにK個のクエリが与えられる。
クエリは２つの数値L,Rからなり、M辺のうちL～R番目のものを取り除いた場合に、グラフが何個の連結要素からなるかを答える。

解法

Union-Findデータ構造を辺の数×2だけ準備する。
まずは、辺が０の状態から１本目、２本目…と辺を増やした場合の点の連結状態をUnion-Findデータ構造で作る。
次に、逆方向に辺が０の状態からM本目、(M-1)本目…と辺を増やした場合のデータ構造を作る。

各クエリL,Rに対しては、1～(L-1)本目までの連結状態と(R+1)～M本目の連結状態をさらにUnionすればよい。

int N,M,K;
int TF[10001][2];

class UF {
	public:
	static const int ufmax=502;
	int ufpar[ufmax],ufrank[ufmax];
	void UF_init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
	int UF_find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = UF_find(ufpar[x]));}
	void UF_unite(int x,int y) {
		x = UF_find(x); y = UF_find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y;
		else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

UF uf[2][10002];

void solve() {
	int f,r,i,j,k,l,x,y;
	int ma=0;
	
	GET2(&N,&M);
	FOR(i,M) {
		TF[i][0]=GETi()-1;
		TF[i][1]=GETi()-1;
	}
	
	FOR(i,10001) {
		uf[0][i].UF_init();
		uf[1][i].UF_init();
	}
	
	FOR(i,M) {
		uf[0][i+1]=uf[0][i];
		uf[0][i+1].UF_unite(TF[i][0],TF[i][1]);
	}
	for(i=M;i>=1;i--) {
		uf[1][i-1]=uf[1][i];
		uf[1][i-1].UF_unite(TF[i-1][0],TF[i-1][1]);
	}
	
	K=GETi();
	FOR(j,K) {
		int l=GETi()-1;
		int r=GETi()-1;
		
		UF tuf1,tuf2;
		tuf1=uf[0][l];
		tuf2=uf[1][r+1];
		FOR(i,N) tuf1.UF_unite(i,tuf2.UF_find(i));
		
		int n=0;
		FOR(i,N) if(tuf1.UF_find(i)==i) n++;
		_P("%d\n",n);
	}
	
	return;
}

まとめ

両側のUnion-Findを合わせりゃいいんじゃね？と考え付けたのは良かった。
残念なのは、手元のUnion-Findライブラリがクラスの形になっておらず１つしかデータを持てなかったため、辺追加毎に複数のデータ構造を持たせられる形になっていなかったこと。

慌ててクラス化したけど、それで若干時間食ったな…。