袜子（并查集）

题目描述

silchen有N只袜子（不区分左右脚）,第i只袜子的颜色是Ci,在接下去的M天，他每天都要穿2只袜子出门。我们知道接下去的第i天，他将会穿编号为ai,bi的2只袜子。
众所周知，每天穿的2只袜子颜色要是一样的。现在silchen有机会更改任意袜子的颜色，他希望可以更改最少的袜子颜色，使得每一天穿的2只袜子颜色相同。

输入

第一行输入一个T，代表数据组数,T小于等于5
每组数据第一行输入2个整数，分别表示n,m,其中n是袜子数量，m是天数，n,m均不大于100000.
第二行输入n个整数，第i个数ci表示第i只袜子颜色,保证ci不大于100000.
接下去m行每行2个整数，表示第i天穿的袜子。

输出

输出一个数字，表示最少更改的袜子数。

样例输入

样例输出

提示

silchen可以把编号为1和3的袜子颜色改成2.

一眼看去并查集，但是没有处理好，思路不对，只是简单的加减了，没有仔细考虑。题目也有点迷惑人，不过可以看出来输入的是下标

思路：可以把下标并起来。然后把每一个下标的颜色放入祖先节点的容器里，跑每一个容器里出现次数最多的颜色，然后 ans += 总颜色 - 最多次数，就是这个容器的修改数。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <string.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <queue>
11 #include <algorithm>
12 #include <sstream>
13 #include <stack>
14 using namespace std;
15 #define rep(i,a,n) for (int i=a;i<n;i++)
16 #define per(i,a,n) for (int i=n-1;i>=a;i--)
17 #define pb push_back
18 #define mp make_pair
19 #define all(x) (x).begin(),(x).end()
20 #define fi first
21 #define se second
22 #define SZ(x) ((int)(x).size())
23 #define FO freopen("in.txt", "r", stdin);
24 #define lowbit(x) (x&-x)
25 #define mem(a,b) memset(a, b, sizeof(a));
26 typedef vector<int> VI;
27 typedef long long ll;
28 typedef pair<int,int> PII;
29 const ll mod=1000000007;
30 const int inf = 0x3f3f3f3f;
31 ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
32 ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
33 //head
34 
35 
36 const int maxn = 100000 + 7;
37 int _, n, m;
38 int c[maxn], father[maxn];
39 VI p[maxn];
40 void init() {
41     for(int i = 1; i <= n; i++) {
42         father[i] = i;
43     }
44 }
45 
46 int find(int x) {
47     if(x == father[x])
48         return x;
49     return father[x] = find(father[x]);
50 }
51 
52 void Union(int x, int y) {
53     int fx = find(x);
54     int fy = find(y);
55     if(fx != fy)
56         father[fx] = fy;
57 } 
58 
59 int main() {
60     for(scanf("%d", &_);_;_--) {
61         mem(p, 0);
62         scanf("%d%d", &n, &m);
63         init();
64         for(int i = 1; i <= n; i++)
65             scanf("%d", &c[i]);
66         int u, v;
67         while(m--){
68             scanf("%d%d", &u, &v);
69             Union(u, v);
70         }
71         for(int i = 1; i <= n; i++) //把每个下标 放入相应的容器
72             p[find(i)].pb(c[i]);
73         int ans = 0;
74         for(int i = 1; i <= n; i++) {
75             if(SZ(p[i]) > 1) {//大于1才处理
76                 int maxx = -1;
77                 map<int, int> mp;//维护出现次数最大值
78                 for(int j = 0; j < SZ(p[i]); j++) {
79                     mp[p[i][j]]++;
80                     maxx = max(maxx, mp[p[i][j]]);
81                 }
82                 ans += SZ(p[i]) - maxx;//非该颜色的数量
83             }
84         }
85         printf("%d
", ans);
86     }
87 }

袜子 （并查集）

袜子（并查集）