Codeforces #376 Div2 C. Socks

不参加でした。今回は実装が軽め。
http://codeforces.com/contest/731/problem/C

問題

N種類の靴下があり、i個目の靴下の色は両足ともC[i]である。
M日間のうちj日目において、左足にはL[j]番、右足にR[j]番の靴下をはく。
一部の靴下の色を塗り替え、毎日左右の靴下の色が同じになるようにしたい。

最少で何組の靴下の色を塗り替えなければならないか。

解法

Union-Findの要領でL[j]とR[j]の靴下を連結していく。
連結した靴下群は同じ色でなければならないため、靴下群の色の登場回数を数え、既に最多登場の色に合わせれば、他の塗り替えるべき靴下の数を最小化できる。

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,K;
int C[202020];
int L,R;
map<int,int> MM[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) cin>>C[i];
	FOR(i,M) {
		cin>>L>>R;
		uf(L-1,R-1);
	}
	
	int ret=0;
	FOR(i,N) MM[uf[i]][C[i]]++;
	FOR(i,N) if(uf[i]==i) {
		int tot=0,ma=0;
		FORR(r,MM[i]) {
			tot+=r.second;
			ma=max(ma,r.second);
		}
		ret += tot-ma;
	}
	cout<<ret<<endl;
}

まとめ

なぜそんな靴下の吐き方をするのか。