CodeForces 731C Socks 并查集-蒲公英云

CodeForces 731C Socks 并查集

Bertha 。 2023-10-11 09:36 90阅读 0赞

1 //题意：有n只袜子，m天，k个颜色，每个袜子有一个颜色，再给出m天，每天有两只袜子，每只袜子可能不同颜色，
 2 //问要让每天的袜子是相同颜色的，要重新染色的袜子数最少是多少。
 3 //
 4 //这里要注意一点，就是他是一次处理完，之后不会继续染色。这就意味着像
 5 //4 3 2
 6 //1 1 2 2
 7 //1 2
 8 //2 3
 9 //3 4
10 //这样的一组数据他只能把全部袜子染色成1或者2；而不能第一天穿1 1，第二天就把前一天穿的2号袜子染色成2
11 //所以也就是说如果这样的一组相互联系起来的袜子它们必须染色成一样的
12 //故下面的思路也得到了证明
13 //
14 //思路：并查集合并，将同一天的袜子合并起来，然后就形成了cnt（就是一个变量）个集合，每个集合都是独立的，因此排序，
15 //找出每个集合里面袜子颜色相同的最多的是哪个颜色，然后把其他不属于这个颜色的都染成这个颜色。
16 //那么这样重新染色的袜子数是最少的，然后每个集合的答案加起来就是最后的结果了。
17 #include<stdio.h>
18 #include<string.h>
19 #include<iostream>
20 #include<algorithm>
21 #include<vector>
22 using namespace std;
23 const int maxn=200010;
24 int v[maxn],w[maxn],root[maxn],vis[maxn];
25 vector<int>r[maxn];
26 int finds(int x)
27 {
28     if(x!=v[x])
29     {
30         int y=finds(v[x]);
31         v[x]=y;
32         return y;
33     }
34     return x;
35 }
36 void unite(int x,int y)
37 {
38     int fx=finds(x);
39     int fy=finds(y);
40     if(fx==fy) return ;
41     v[fx]=fy;
42 }
43 int main()
44 {
45     int n,m,k;
46     scanf("%d%d%d",&n,&m,&k);
47     for(int i=1;i<=n;++i)
48     {
49         v[i]=i;
50         scanf("%d",&w[i]);
51     }
52     while(m--)
53     {
54         int x,y;
55         scanf("%d%d",&x,&y);
56         vis[x]=vis[y]=1;
57         unite(x,y);
58     }
59     int cnt=0;
60     for(int i=1;i<=n;++i)
61     {
62         if(vis[i])
63         {
64             if(v[i]==i) root[++cnt]=i;
65             r[finds(i)].push_back(w[i]);
66         }
67     }
68     int ans=0;
69     for(int i=1;i<=cnt;++i)
70         sort(r[root[i]].begin(),r[root[i]].end());
71     for(int i=1;i<=cnt;++i)
72     {
73         int now=1,tmp=0;
74         for(int j=1;j<r[root[i]].size();j++)
75         {
76             if(r[root[i]][j]!=r[root[i]][j-1])
77             {
78                 tmp=max(tmp,now);
79                 now=1;
80             }
81             else now++;
82         }
83         tmp=max(now,tmp);
84         ans+=r[root[i]].size()-tmp;
85     }
86     printf("%d\n",ans);
87     return 0;
88 }