yukicoder : No.416 旅行会社

No.417の方が簡単だった。
http://yukicoder.me/problems/no/416

問題

1～Nの頂点とM本の無向辺からなるグラフと、Q個のクエリが与えられる。
各クエリは、辺を１つ指定するもので、順に辺を削除していく。

各頂点iについて、辺を順に削除していく過程で、頂点1と非連結になるのはどのクエリを実行した直後か答えよ。

解法

連結状態を管理する問題なので、Union-Findが真っ先に思い浮かぶ。
ただしUnion-Findは連結済みの要素を分解することができない。

そこで、以下の順でUnion-Findによる連結を行い、初めて1番の頂点と連結したタイミングを求めよう。

• クエリで含まれない（＝最後まで削除されない）辺を連結する。
• クエリを逆順で処理し、辺を追加していく。

なお、この過程で連結状態だけでなく各連結成分に含まれる成分の一覧を管理する必要がある。
(クエリを逆順で処理する過程で、初めて1番の頂点と連結した段階で、その連結成分である頂点が初めて非連結になったタイミングがわかるため)

愚直に一覧を連結すると最悪O(N)要素の一覧をO(N)回連結するため時間がO(N^2)かかりTLEする。
ここはいわゆるマージテクを用いることで連結を軽量化しよう。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

int N,M,Q;
int R[101010];
int X[201010],Y[202020];
set<pair<int,int>> E;

vector<int> V[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,M) {
		cin>>x>>y;
		E.insert({x-1,y-1});
	}
	FOR(i,Q) {
		cin>>X[i]>>Y[i];
		X[i]--,Y[i]--;
		E.erase({X[i],Y[i]});
	}
	
	FORR(r,E) uf(r.first,r.second);
	FOR(i,N) V[uf[i]].push_back(i);
	FOR(i,N) if(uf[0]==uf[i]) R[i]=-1;
	
	for(i=Q-1;i>=0;i--) if(uf[X[i]] != uf[Y[i]]) {
		x=uf[X[i]];
		y=uf[Y[i]];
		if(x==uf[0]) FORR(r,V[y]) R[r]=i+1;
		if(y==uf[0]) FORR(r,V[x]) R[r]=i+1;
		
		if(V[x].size()<V[y].size()) swap(x,y);
		FORR(r,V[y]) V[x].push_back(r);
		V[y].clear();
		uf(x,y);
		if(uf[x]==y) swap(V[x],V[y]);
		
	}
	FOR(i,N-1) cout<<R[i+1]<<endl;
	
}

まとめ

分割できるUnion-Find欲しい。