题解：P14077 [GESP202509 七级] 连通图

· · 题解

P14077 [GESP202509 七级] 连通图

这是我的第一篇题解，求求点个赞吧！

一、题面解析

给定一张n个节点、m条边的无向图，求出要使整个图联通最少需要增加几条边。
题目可以转化成要使所有连通块联通要几条边，就还可以转化成 连通块数量-1！
因此，我们使用小学二年级就学过的转化思想将复杂的体面转化成了简单的问题：连通块数量-1。
只是不会转化但会数连通块的数量的同学们已经退了，但有一些蒟蒻就问了：怎么求出连通块的数量呢？

二、题目思路

样例1

我们先从简单一点的样例开始看： 

4 0

不难数出，我们只需要增加点数-1条边，也就是4-1=3条边就可以了，因为每个连通块里面只有一个点：

样例2

接下来我们看一个不一样的样例； 

2 1
1 2

在这里的时候，点1和点2形成了一个连通块，这时我们不能重复访问，所以我定义了一个leave数组表示一个点是否访问过，当leave[i]==true时点i就已经访问过了，因此我们可以写出如下代码：

bool leave[MAXN];
for(int i=1;i<=n;i++){
    //进行连通块遍历
    if(leave[i]==true){
        //已经访问过了，跳过防止重复计算
        continue;
    }
    ans++;//连通块数量+1
    f(i);//开始遍历
}
ans--;//需要增加的边数=连通块数量-1
cout<<ans;
return 0;

在上面的代码中，有一个函数f(x)，它是用来进行连通块的遍历的，那么他怎么写呢？

样例3

4 2
1 2
3 4

在这里，我们可以用伪代码来帮助我们疏通思路：

void f(int x){
    将点x标记为已访问;
    for(int i=0;i<与x为邻边关系的点的数量;i++){
        用变量u来存储这个点;
        if(这个点已访问){
            跳过此次循环;
        }
        f(u);
    }
    return;
}

当然存储每条边可以用邻接矩阵，可以用邻接表，也可以用链式前向星等，我这里使用邻接表，比较简洁方便。
邻接表：

vector<int> edge[MAXN];//邻接表
for(int i=1;i<=m;i++){
    int u,v;//表示无向边的两个点
    cin>>u>>v;
    //将无向边变成双向的有向边
    edge[u].push_back(v);//正向建边
    edge[v].push_back(u);//反向建边
}
return 0;

遍历函数f(x)：

void f(int x){
    leave[x]=true;//标记为已访问
    for(int i=0;i<edge[x].size();i++){
        //遍历与点x有邻边关系的点
        int u=edge[x][i];//用变量u来存储这个点
        if(leave[u]==true){
            //已访问过，跳过访问
            continue;
        }
        f(u);//继续进行遍历
    }
    return;
}

样例4

4 4
1 2
2 3
3 4
4 1

不难看出这个样例的结果为0，因为他已经是一个完全联通的图了，有的同学可能会输出1，记得检查一下ans有没有减1，因为增加的边数是连通块个数-1。

三、完整代码

完整代码（含完整注释）：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m,ans=0;//ans表示需要加的边数（连通块数-1）
vector<int> edge[MAXN];//邻接表
bool leave[MAXN];
void f(int x){
    leave[x]=true;//标记为已访问
    for(int i=0;i<edge[x].size();i++){
        //遍历与点x有邻边关系的点
        int u=edge[x][i];//用变量u来存储这个点
        if(leave[u]==true){
            //已访问过，跳过访问
            continue;
        }
        f(u);//继续进行遍历
    }
    return;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;//表示无向边的两个点
        cin>>u>>v;
        //将无向边变成双向的有向边
        edge[u].push_back(v);//正向建边
        edge[v].push_back(u);//反向建边
    }
    for(int i=1;i<=n;i++){
        //进行连通块遍历
        if(leave[i]==true){
            //已经访问过了，跳过防止重复计算
            continue;
        }
        ans++;//连通块数量+1
        f(i);//开始遍历
    }
    ans--;//需要增加的边数=连通块数量-1
    cout<<ans;
    return 0;
}

这篇题解真的花费了我很多心思和时间，求大家点一个免费的赞再走吧！管理员求过！