Codeforces Round #385 (Div. 1), problem: (A) Hongcow Builds A Nation 【dfs】

一百个Chocolate · CSDN · · 2020-02-05 19:16

题意

在一个星球上，有n个点，m条边，其中有k个点是不同国家的政府。要求结点没有到自己的边，任意两个结点间只存在一条边，任意两个政府点之间不存在路径。问满足上面三个条件下，最多往图中添加几条边。

思路

先利用已给的边求出每个政府树的顶点数（dfs）
选出顶点数最多的政府树，将剩余的与政府点不连通的点加入该树
此时所有的点被分为k组，将每组中的点全部连同，可以得到最大总边数，减去已有边就是答案。

code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
int n,m,k;
int vis[maxn];
int a[maxn],vn,vmax,ans;
vector<int>G[maxn];
void dfs(int u){
    vn++;
    vis[u]=1;
    for(auto v:G[u])
        if(!vis[v]&&v!=u)
            dfs(v);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=k;i++){
        vn=0; //初始化与该政府顶点同树的点  
        dfs(a[i]);
        ans+=vn*(vn-1)/2; //先将每个政府顶点所在树上的点全部相连
        n-=vn; //剩余和任何政府顶点都没有关系的点
        vmax=max(vmax,vn);  //找出所有政府顶点所在树中顶点数最多的树 
    }
    ans+=n*(n-1)/2; //将剩余所有无法到达政府顶点的点相互连接
    ans+=n*vmax; //将这些点与已有的点数最多的政府顶点树相连
    ans-=m;		//减去已有的边
    cout<<ans<<endl;
    return 0;
}