用DFS的方法求图连通分量个数

用DFS的方法求图中连通分量的个数

原本很简单的一题思考了很久，这就是写伪代码写多了的后果
很多关于道路的题目，什么顶点相连接的题目都能用到关于图的方法

先讲最最基本的没有任何优化的方法，优化后续考虑

流程

初始化一个二维数组用来存储无向图G[ ][ ]

初始化记录连通分量个数的int count=0

从任意顶点开始DFS，通过这个顶点遍历到的所有顶点都属于同一个连通分量，对于DFS的细节：这些遍历到的顶点要做好标记，表示已经被访问过

void dfs(int k){
    visited[k]=1;
    //记录所属的连通分量的编号
    //id[k]=cnt2;
    for(int i=1;i<=n;i++){
        if(G[k][i]==1 && visited[i]==0){
            cnt++;//分量内的点的个数
            dfs(i);
        }
    }
}

从没有访问过的顶点取出一个顶点，重复DFS，遍历完成之后count++，这就需要两个函数，不仅仅DFS，还有一个计数函数

void count(int n){
    for(int i=1;i<=n;i++){
        if(visited[i]==0){
            dfs(i);
            cnt2++;
        }
    }
}

输出count，这个就是图中连通分量的个数（cnt2）

代码

题目链接：3719. 畅通工程 - AcWing题库

#include<iostream>
#include<cstring>
using namespace std;
int cnt=0,cnt2=0,n,m,cin1,cin2;
int visited[1000];
int G[1005][1005];
void dfs(int k){
    visited[k]=1;
    for(int i=1;i<=n;i++){
        if(G[k][i]==1 && visited[i]==0){
            cnt++;//分量内的点的个数
            dfs(i);
        }
    }
}

void count(int n){
    for(int i=1;i<=n;i++){
        if(visited[i]==0){
            dfs(i);
            cnt2++;
        }
    }
}
int main(){
    //memset(visited,0,sizeof(visited));
    //memset(G,0,sizeof(G));
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> cin1 >> cin2;
        G[cin1][cin2]=1;
        G[cin2][cin1]=1;
    }

    //dfs(1);
    count(n);
    //cout << cnt << endl;
    cout << cnt2-1 << endl;
    return 0;
}

参考

https://blog.csdn.net/qq_40438165/article/details/88540261