CF #376 (Div. 2) C. dfs

2、题意：给袜子上色，使n天左右脚袜子都同样颜色。

3、总结：一开始用链表存图，一直TLE test 6

(1)如果需要高效的随即存取，而不在乎插入和删除的效率，使用vector 。

(2)如果需要大量的插入和删除，而不关心随即存取，则应使用list 。

#include<bits/stdc++.h>
#define F(i,a,b) for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
using namespace std;
const int N=200100,MAX=1000100;

int n,m,k,vis[N],col[N],sum,sum1,maxn;
map<int ,int >M;
vector<int >G[N];

void dfs(int u)
{
    vis[u]=1;   M[col[u]]++;
    //sum++;    //直接在map::M上遍历时间会优化一点
    //if(maxn<M[col[u]]) maxn=M[col[u]];
    for(int v:G[u]) if(!vis[v]) {   //才发现for可以这样简写
        dfs(v);
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    FF(i,1,n) scanf("%d",&col[i]);
    int l,r;
    FF(i,1,m) {
        scanf("%d%d",&l,&r);
        G[l].pb(r); G[r].pb(l);
    }
    mes(vis,0);  sum1=0;
    FF(i,1,n) if(!vis[i]) {
        M.clear();
        sum=maxn=0;
        dfs(i);
        for(auto p:M){
            sum+=p.second;
            if(maxn<p.second) maxn=p.second;
        }
        sum1+=(sum-maxn);
    }
    cout<<sum1<<endl;

    return 0;
}

View Code