SoundHound Programming Contest 2018 Masters Tournament 本戦 : D - Propagating Edges

これはタイムラインを見ていたために、ヒントありで状態で取り組んだのでさっくり。
https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_d

問題

初期状態でN頂点0辺の無向グラフがある。
以下順次クエリを処理せよ。

• 2頂点u,v間に辺がなければ追加する。
• 点vが指定される。vの連結した頂点の対a,bに対し、a-b間に辺がなければ辺を追加する。
• 2頂点u,vが指定されるので、両者を直接つなぐ辺があるか判定する。

解法

Union-Findとマージテクを用いる。
まず、1つめのクエリで直接結ばれた頂点対はset等で管理しよう。
以下２つのUnion-Findデータ構造を用いる。

• 1つめは、1つめのクエリによる連結判定を行うのに用いる。
• 2つめは、2つめのクエリにより完全グラフを成す成分集合を表すのに用いる。

また、各頂点はsetのマージテクにより、1つめの観点における連結成分の頂点一覧を管理しよう。

• 1つめのクエリについては、1つめのデータ構造をUniteしつつ、マージテクで頂点集合を合わせていこう。
• 2つめのクエリについては、前述の頂点集合内の頂点を2つめのデータ構造においてUniteする。その後は、頂点集合は1頂点だけ残し消してしまってよい。
• 3つめのクエリについては、1つめのクエリで直接結ばれているか、2つめのデータ構造において同じグループに属するかを判定すればよい。

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,uf2;

set<int> S[101010];
set<pair<int,int>> E;
int N,Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) S[i+1].insert(i+1);
	while(Q--) {
		cin>>i>>x>>y;
		if(i==1) {
			E.insert({x,y});
			E.insert({y,x});
			
			x=uf[x];
			y=uf[y];
			if(x!=y) {
				if(S[x].size()<S[y].size()) swap(S[x],S[y]);
				FORR(s,S[y]) S[x].insert(s);
				S[y].clear();
				uf(x,y);
				if(uf[x]==y) swap(S[x],S[y]);
			}
		}
		else if(i==2) {
			x=uf[x];
			FORR(s,S[x]) uf2(s,x);
			S[x].clear();
			S[x].insert(x);
		}
		else if(i==3) {
			if(E.count({x,y}) || uf2[x]==uf2[y]) cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
	}
}

まとめ

本番の緊張感だとすんなりは解けなかったかも。