Codeforces 744C【DFS】

题意：

给你一幅图，然后有几个特殊点和不特殊点，给你一些已经连了的边，在保证特殊点不能连的前提下，问最多还能添几条边，双向边

思路：

简单题，就是一个特殊点就是一个集合，然后搜一下，最后把还有没连的点连到集合元素最多的上去，然后把所有边都算出来，减去已经连的边就好了

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e3+10;

const int M=1e5+10;

struct asd{

    int to;

    int next;

};

asd q[M*2];

int head[M*2],tol,num;

bool spe[N];

int pp[N];

bool vis[N];

void add(int u,int v)

{

    q[tol].to=v;

    q[tol].next=head[u];

    head[u]=tol++;

}

void dfs(int u,int pre)

{

    for(int i=head[u];i!=-1;i=q[i].next)

    {

        int to=q[i].to;

        if(vis[to]) continue;

        vis[to]=1;

        pp[pre]++;

        num--;

        dfs(to,pre);

    }

}

int main()

{

    int x;

    int n,m,k;

    scanf("%d%d%d",&n,&m,&k);

    memset(spe,0,sizeof(spe));

    memset(pp,0,sizeof(pp));

    num=n-k;

    for(int i=1;i<=k;i++)

    {

        scanf("%d",&x);

        spe[x]=1;

        pp[x]=1;

    }

    memset(head,-1,sizeof(head));

    tol=0;

    int u,v;

    for(int i=0;i<m;i++)

    {

        scanf("%d%d",&u,&v);

        add(u,v);

        add(v,u);

    }

    memset(vis,0,sizeof(vis));

    for(int i=1;i<=n;i++)

    {

        if(spe[i])

        {

            vis[i]=1;

            dfs(i,i);

        }

    }

    int mm=-1,kk;

    for(int i=1;i<=n;i++)

    {

        if(mm<pp[i]&&pp[i])

        {

            kk=i;

            mm=pp[i];

        }

    }

    pp[kk]+=num;

    int ans=0;

    for(int i=1;i<=n;i++)

        if(spe[i])

            ans+=(pp[i]-1)*pp[i]/2;

    printf("%d\n",ans-m);

    return 0;

}

巴特西

Codeforces 744C【DFS】

最新文章

热门文章