Codeforces #396 Div2 D. Mahmoud and a Dictionary

割と典型。
http://codeforces.com/contest/766/problem/D

問題

N個の単語と、M個の関係とQ個のクエリが与えられる。

各関係は、2つの単語が同じ意味を示すか、また異なる意味を示すかで構成される。
それまでに登場した関係と矛盾するかどうかを答えよ。
矛盾する場合、以後その関係は無視してよい。

その後、各クエリでは2つの単語が与えられる。
両単語は同じ意味を示すか、異なる意味を示すか、それともどちらでもないかを示せ。

解法

Union-Findで2N個の頂点を連結していく。
以下の問題とほぼ同じ。単語の意味の等しい・異なるが、長さの偶奇に置き換わっただけ。
AtCoder ARC #036 : D - 偶数メートル - kmjp's blog

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;
map<string,int> S;
int N,M,Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,N) cin>>s, S[s]=i;
	while(M--) {
		string A,B;
		cin>>i>>A>>B;
		x=S[A];
		y=S[B];
		if(i==1) {
			if(uf[x*2]==uf[y*2+1]) {
				cout<<"NO"<<endl;
			}
			else {
				cout<<"YES"<<endl;
				uf(x*2,y*2);
				uf(x*2+1,y*2+1);
			}
		}
		else {
			if(uf[x*2]==uf[y*2]) {
				cout<<"NO"<<endl;
			}
			else {
				cout<<"YES"<<endl;
				uf(x*2,y*2+1);
				uf(x*2+1,y*2);
			}
		}
	}
	while(Q--) {
		string A,B;
		cin>>A>>B;
		x=S[A];
		y=S[B];
		if(uf[x*2]==uf[y*2]) cout<<1<<endl;
		else if(uf[x*2]==uf[y*2+1]) cout<<2<<endl;
		else cout<<3<<endl;
	}
	
	
}

まとめ

うーん。