Codeforces #464 Div2 D. Love Rescue

Codeforces多すぎ。
http://codeforces.com/contest/939/problem/D

問題

２つの文字列がある。
ある文字を他の文字に一斉に変える、ということを繰り返し文字列を同じにしたい。
最小何回文字の変更を行えばよいか。

解法

同じ位置同士を見比べて、Union-Findで異なるグループに異なる文字が同時に登場したらUniteしていくだけ。

int N;
string S,T;

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;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>T;
	vector<vector<char>> V;
	
	FOR(i,N) {
		if(uf[S[i]]!=uf[T[i]]) {
			V.push_back({(char)uf[S[i]],(char)uf[T[i]]});
			uf(S[i],T[i]);
		}
	}
	cout<<V.size()<<endl;
	FORR(v,V) cout<<v[0]<<" "<<v[1]<<endl;
}

まとめ

問題文解釈も込みだと、Cの方がはるかに苦戦した。