Codeforces 731C Socks 并查集

题目：http://codeforces.com/contest/731/problem/C

思路：并查集处理出哪几堆袜子是同一颜色的，对于每堆袜子求出出现最多颜色的次数，用这堆袜子的数目减去该值即为这堆袜子需要修改的颜色数，用同样的方法处理每堆求和即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int f[222222],c[222222];
 4 map<int,map<int,int> > mp;
 5 int getf(int x){
 6     if(f[x] == x)
 7         return x;
 8     else
 9         return f[x] = getf(f[x]);
10 }
11 void merge(int u,int v){
12     int a = getf(u);
13     int b = getf(v);
14     if(a != b)
15         f[b] = a;
16 }
17 int main(){
18     int n,m,k;
19     cin >> n >> m >> k;
20     for(int i = 1;i<=n;i++){
21         f[i] = i;
22         scanf("%d",&c[i]);
23     }
24     int l,r;
25     while(m--){
26         scanf("%d%d",&l,&r);
27         merge(l,r);
28     }
29     for(int i = 1;i<=n;i++){
30         mp[getf(i)][c[i]]++;
31     }
32     int ans = 0;
33     for(map<int,map<int,int> >::iterator i = mp.begin();i!=mp.end();i++){
34         int sum = 0,mx = 0;
35         for(map<int,int>::iterator j = i->second.begin();j!=i->second.end();j++){
36             mx = max(mx,j->second);
37             sum += j->second;
38         }
39         ans += sum-mx;
40     }
41     cout << ans;
42     return 0;
43 }