CodeForces 731C Socks

Time limit exceeded 了5次，并查集+路径压缩+Vector优化+Map优化，才过了这一题。

题目链接CodeForces 731C

题目大意

n个袜子，m天，k种颜色，保证每天穿的袜子颜色都一样，最少需要给几个袜子改颜色。

题目解析

第一感觉是用贪心，但是细想之后发现很难处理，一个袜子可能穿多次，不同袜子可能有相同颜色，一天一天分析的话若是修改某一个袜子颜色会牵扯很多。上网查了一下，发现是并查集，仔细想了一下，并查集确实可以解决这个问题。具有相同袜子的某几天颜色必须都一样，这些袜子构成一个集合。比如第一天1,2、第二题2,3，那么1,2,3是一个集合，他们颜色必须一样，最少的涂法就是集合数减去最大的具有相同颜色的袜子的数目。
但是想明白了这一点也还是不好写，因为正常的写法会T。本题n<2000000,而且可能会出现多个集合，你要先遍历找出并查集的根，然后遍历找到属于这个根的元素，然后统计这些元素中最大颜色数。这样的步骤一定会超时，所以要尽可能的优化程序。

1. 首先是路径压缩，这样每次找某个元素的所属时就不需要用函数了，直接用数组就行了，注意路径压缩要在并查集构造完之后再执行一遍finds函数，否则的话其实还没有完全更新路径；
2. 其次是map优化,颜色的代号是数字，一单集合中出现某种颜色，则map<颜色代号>++,边加边找最大值即可；
3. 然后是vector优化，提前将某一个根的元素都储存在vector[bin[i]]中，这样就避免了for循环找根然后再for循环找所属元素的情况了。

AC代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int bin[200010],color[200010];
int finds(int x) //查
{
        int r=x;
        while(bin[r]!=r)
        {
                r=bin[r];
        }
        int rx=x;
        while(rx!=r) //路径压缩
        {
                int ry=bin[rx];
                bin[rx]=r;
                rx=ry;
        }
        return r;
}
void merges(int x,int y) //并
{
        int fx=finds(x);
        int fy=finds(y);
        if(fx!=fy)
        {
                bin[fx]=fy;
        }
}
vector<int> col[200100];
int main()
{
        int n,m,k;
        scanf("%d %d %d",&n,&m,&k);
        for(int i=1;i<=n;i++)
        {
                scanf("%d",&color[i]);
                bin[i]=i;
        }
        while(m--)
        {
                int x,y;
                scanf("%d %d",&x,&y);
                merges(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;i++) int X=finds(i); //并查集建立后更新路径
        for(int i=1;i<=n;i++) //押入容器
        {
                col[bin[i]].push_back(i);
        }
        map<int,int> mp; //求最多的颜色的数目
        for(int i=1;i<=n;i++)
        {
                if(col[i].size()==1) continue;
                int m=col[i].size();
                mp.clear();
                int mx=0;
                for(int j=0;j<m;j++)
                {
                        int x=col[i][j];
                        mp[color[x]]++;
                        mx=max(mp[color[x]],mx);
                }
                ans+=m-mx;
        }
        printf("%d\n",ans);
        return 0;
}