CodeForces 731C Socks

http://codeforces.com/problemset/problem/731/C

并查集+贪心 将要求颜色相同的袜子序号放入一个集合中

贪心：然后统计这个集合中出现次数最多但颜色 可以得到这个集合要repain的次数

代码有难度

统计集合数

int tot;//总的集合数

for (int i = 1; i <= n; i++)

　　if(par[i] == i)

{

　　rec[tot++] = i;//记录根节点

}

//统计每个集合红颜色的个数

map<int, int> clmp;

vector<int> G[MAXN];

for(int i = 1; i <= n; i++)

{

　　G[par[i]].push_back(color[i]);

}

int ans = 0;

for(int i = 0; i < tot; i++)//统计颜色情况

{

　　clmp.clear();

　　for (int j = 0; j < v[rec[i]].size(); j++)

　　clmp[v[rec[i]][j]]++;

}

 #include <bits/stdc++.h>
 #define MAXN 200007
 using namespace std; int par[MAXN]; int find(int x)
 {
     if (par[x] == x) return x;
     else return par[x] = find(par[x]);
 }
 bool same(int x, int y)
 {
     int px, py;
     px = find(x);
     py = find(y);
     return px == py;
 }
 void unite(int x, int y)
 {
     int px = find(x);
     int py = find(y);
     par[px] = py;
 }
 int color[MAXN];
 int rec[MAXN];
 vector<int> v[MAXN];
 map<int,int> clmap;
 int main()
 {
     int day, paint, socks, ans = ;
     scanf("%d%d%d", &socks, &day, &paint);
     for (int i =  ;  i <= socks; i++) par[i] = i;
     for (int i = ; i <= socks; i++)
     {
         scanf("%d", &color[i]);
     }
     for (int i = ; i < day; i++)
     {
         int l, r;
         scanf("%d%d", &l, &r);
         unite(l, r);
     }
     int tot = ;
     for (int i = ; i <= socks; i++)
     {
         if (i == find(i))
         {
             rec[tot++] = i;
         }
     }
     for (int i = ; i <= socks; i++)
     {
         v[par[i]].push_back(color[i]);
     }
     for (int i = ; i < tot; i++)
     {
         clmap.clear();
         for(int j = ; j < v[rec[i]].size(); j++)
         {
             clmap[v[rec[i]][j]]++;
         }
         map<int,int> :: iterator it;
         int maxn = ;
         for (it = clmap.begin(); it != clmap.end(); it++)
         {
             maxn = max(maxn, (*it).second);
         }
         ans += v[rec[i]].size() - maxn;
     }
     cout << ans << endl;
 }