并查集问题

1248762042

★问题描述
皮卡丘一共有N只袜子，袜子共有K种颜色(当然一只袜子只有一种颜色)（K<=N）。爱卫生的皮卡丘在连续M天中每天都要穿两只颜色相同的袜子，如果皮卡丘某天拿到了两只颜色不同的袜子，它就会施展魔法改变袜子颜色使得两只袜子变成相同颜色。

现给出皮卡丘在M天内每天要穿的两只袜子的序号，问它最少需要修改几只袜子的颜色才能达到目的。

★数据输入
输入第一行包括三个正整数 N，M，K（2<=N<=200000，0<=M<=200000,1<=K<=200000）。

第二行输入 N 个正整数 C1,C2,C3...CN(1<=Ci<=K)，表示每只袜子的颜色。

接下来M行，每行两个正整数 li，ri (1<=li,ri<=N) 表示皮卡丘在M天内每天要穿的袜子序号。

★数据输出
输出一个整数，为皮卡丘需要修改颜色的袜子的最少只数。

★输入示例
3  2  3
1  2  3
1  2
2  3
★输出示例
2

zy8818

你这个文字讲的太难理解了
现给出皮卡丘在M天内每天要穿的两只袜子的序号，问它最少需要修改几只袜子的颜色才能达到目的
每天穿两个袜子不同颜色只要施展魔法变一次就变成相同颜色了？你所说的目的是什么》？是所有的袜子要全部变成一样的目的还是每天变变多少天吗？

1248762042

zy8818 发表于 2021-11-13 20:19
你这个文字讲的太难理解了
现给出皮卡丘在M天内每天要穿的两只袜子的序号，问它最少需要修改几只袜子的颜 ...

就是比如 第一天穿 1 2  第二天穿 1 2 那只要第一天把序号1的袜子颜色改成颜色 2 那第二天就不用改了,只修改了一次

傻眼貓咪

题目看似简单，实则困难：

思路
首先，假设某天袜子颜色不一，必须解决该改变的袜子颜色（2 选 1），如同题目要求，以最少改变次数作答（虽然每次 2 选 1，但该选择哪里一个袜子，最终都会大大影响全局袜子变数）
其二，范本太大，每项少于 200000，如果可以直接以组合公式算还好，但这题目给定每日袜子颜色不定，变数超级大，无论是内存空间，时间复杂度都大大提升

注：一般这种题目，除非数学超级好，否则大佬们都会视而不见，毕竟数学和程序代码是 2 个不同领域的学问

1248762042

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. const int veryBig=200005;
   
6. 
   
7. vector<int> Boss[veryBig];
   
8. int Function[veryBig];
   
9. int Amazing[veryBig];
   
10. 
    
11. 
    
12. int wanting(int Value) {
    
13.         if ( Value != Function[Value] )
    
14.         {
    
15.                 Function[Value] = wanting( Function[Value] );
    
16.         }
    
17.         return Function[Value];
    
18. }
    
19. 
    
20. void Unity(int first,int second) {
    
21.        
    
22.         int A = wanting(first);
    
23.         int B = wanting(second);
    
24.        
    
25.         if (A != B)
    
26.         {
    
27.                 Function[B] = A;
    
28.         }
    
29.        
    
30. }
    
31. 
    
32. void Play()
    
33. {
    
34.         int Number;
    
35.         int Days;
    
36.         int Color;
    
37.         int Left;
    
38.         int Right;
    
39.         int total;
    
40.        
    
41.         cin >> Number >> Days >> Color;
    
42.        
    
43.         for (int i = 1; i <= Number; i++) {
    
44.                 Function[i] = i;
    
45.                 cin >> Amazing[i];
    
46.         }
    
47.         for (int i = 1; i <= Days; i++) {
    
48.                 cin >> Left >> Right;
    
49.                 Unity(Left,Right);
    
50.         }
    
51.         for (int i = 1; i <= Number; i++) {
    
52.                 Boss[wanting(i)].push_back(Amazing[i]);
    
53.         }
    
54. 
    
55.         for (int i = 1; i <= Number; i++) {
    
56.                
    
57.                 int Length;
    
58.                 Length = Boss[i].size();
    
59.                 int Max;
    
60.                 Max = 0;
    
61.                
    
62.                 if (Length > 1) {
    
63.                         map <int,int> sum;
    
64.                         for (int j = 0; j<Length; j++) {
    
65.                                 sum[Boss[i][j]]++;
    
66.                                 Max = max( Max, sum[Boss[i][j]]);
    
67.                         }
    
68.                         total += ( Length - Max );
    
69.                 }
    
70.                
    
71.                 Boss[i].clear();
    
72.                
    
73.         }
    
74.         cout << total;
    
75. }
    
76. 
    
77. int main() {
    
78.         Play();
    
79. }

复制代码

1248762042

1248762042 发表于 2021-11-16 19:40

写出来了