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=,MAX=;

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]=;   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,,n) scanf("%d",&col[i]);

    int l,r;

    FF(i,,m) {

        scanf("%d%d",&l,&r);

        G[l].pb(r); G[r].pb(l);

    }

    mes(vis,);  sum1=;

    FF(i,,n) if(!vis[i]) {

        M.clear();

        sum=maxn=;

        dfs(i);

        for(auto p:M){

            sum+=p.second;

            if(maxn<p.second) maxn=p.second;

        }

        sum1+=(sum-maxn);

    }

    cout<<sum1<<endl;

    return ;

}

秒客网

CF #376 (Div. 2) C. dfs

相关文章