TopCoder SRM 640 Div1 Easy ChristmasTreeDecoration

SRM640に参加。
Easyをそこそこ速く解いたつもりだが、Mediumが解けずレート減。
http://community.topcoder.com/stat?c=problem_statement&pm=13551

問題

N本の木を(N-1)本のリボンで１つにつなぎたい。
1つのリボンで２つの木をつなぐことができるが、つなぐことのできるペアは決まっており、入力として与えられる。

ここで、それぞれの木の飾りの色が与えられる。
リボンで木をつなぐときは、異なる色の木同士を結びたい。
同じ色を結ばざるを得ない最小のリボンの数を答えよ。

なお、全ての木をつなげられることは保証されている。

解法

異なる色の木をつなぐリボンを使い、Union-Findで出来るだけ連結していく。
最終的に得られる連結した木の集合は、あとは同じ色同士をつながないと連結できない木を意味する。
よって連結した木の集合の数から1引いたものが解。

class UF {
	public:
	static const int ufmax=152;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[find(x)];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

class ChristmasTreeDecoration {
	public:
	int solve(vector <int> col, vector <int> x, vector <int> y) {
		int i,j,k,ret=0;
		UF uf;
		FOR(i,x.size()) if(col[x[i]-1]!=col[y[i]-1]) uf.unite(x[i]-1,y[i]-1);
		FOR(i,col.size()) if(uf[i]==i) ret++;
		return ret-1;
	}

まとめ

本番ちょっと回りくどい実装をしてしまった。