并查集问题

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

#include <bits/stdc++.h>

using namespace std;

const int veryBig=200005; 

vector<int> Boss[veryBig];
int Function[veryBig];
int Amazing[veryBig];


int wanting(int Value) {
        if ( Value != Function[Value] ) 
        {
                Function[Value] = wanting( Function[Value] );
        }
        return Function[Value];
}

void Unity(int first,int second) {
        
        int A = wanting(first);
        int B = wanting(second);
        
        if (A != B)
        { 
                Function[B] = A;
        }
        
}

void Play()
{
        int Number;
        int Days;
        int Color; 
        int Left;
        int Right;
        int total;
        
        cin >> Number >> Days >> Color;
        
        for (int i = 1; i <= Number; i++) {
                Function[i] = i;
                cin >> Amazing[i];
        }
        for (int i = 1; i <= Days; i++) {
                cin >> Left >> Right;
                Unity(Left,Right);
        }
        for (int i = 1; i <= Number; i++) {
                Boss[wanting(i)].push_back(Amazing[i]);
        }

        for (int i = 1; i <= Number; i++) {
                
                int Length;
                Length = Boss[i].size();
                int Max;
                Max = 0;
                
                if (Length > 1) {
                        map <int,int> sum;
                        for (int j = 0; j<Length; j++) {
                                sum[Boss[i][j]]++;
                                Max = max( Max, sum[Boss[i][j]]);
                        }
                        total += ( Length - Max );
                }
                
                Boss[i].clear();
                
        }
        cout << total; 
}

int main() {
        Play();
}

1248762042

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

写出来了