题目链接：http://codeforces.com/problemset/problem/731/C
题意：有n只袜子，每只都有一个颜色，现在他的妈妈要去出差m天，然后让他每天穿第 L 和第 R 只袜子，他为了让每天穿的袜子都是一个颜色的，他需要把袜子涂色，共有k种颜色，求最少需要涂多少只袜子，才能保证他每天穿的袜子都是一样的.
用并查集把所有联系在一起的袜子放到一个集合中去，然后这些袜子会变成一块一块的，我们在每一块中找一种颜色最多的，然后把当前块中的其他袜子都涂成这种颜色即可，累加即可
#include<iostream> #include<algorithm> #include<math.h> #include<string.h> #include<stdio.h> #include<map> #include<vector> #include<queue> using namespace std; #define met(a, b) memset(a, b, sizeof(a)) #define mod 1000000007 typedef long long LL; ////////////////////////////////////////////////////////////// const int INF = 0x3f3f3f3f; const int N = 200521; const double eps = 1e-8; int m, n, k, fa[N], r[N], a[N]; vector<int> G[N]; int Find(int u) { if(fa[u] != u) return fa[u] = Find(fa[u]); return fa[u]; } int main() { while(scanf("%d %d %d", &n, &m, &k)!=EOF) { for(int i=1; i<=n; i++) { scanf("%d", &a[i]); fa[i] = i; } for(int i=1; i<=m; i++) { int u, v; scanf("%d %d", &u, &v); int pu = Find(u); int pv = Find(v); if(pu != pv)///先放到一个集合中去; fa[pu] = pv; } for(int i=0; i<=n; i++) G[i].clear(); for(int i=1; i<=n; i++) { int k = Find(i); G[k].push_back(i);///构建一个以i的根节点的集合； } int ans = 0; for(int i=1; i<=n; i++) { map<int, int> cnt;///记录各种颜色的个数; int len=G[i].size(), Max = 0;///Max是颜色最多的; for(int j=0; j<len; j++) { int v = G[i][j]; cnt[a[v]]++; Max = max(Max, cnt[a[v]]); } ans += len - Max;///累加结果; } printf("%d ", ans); } return 0; }