1. 连通块的定义
块内每个点之间都有一条路径。
2. 思路
- 我们可以用dfs深度优先搜索：从一个点出发遍历图将遍历过的点全部标记，标记过的点则不会再遍历到。
- 再写一个循环枚举所有的点（枚举起点），如果没标记就代表可以作为起点，数量加一，进行dfs标记点。
3. 代码 文章来源：https://www.toymoban.com/news/detail-644054.html
#include<bits/stdc++.h>
using namespace std;
long long n,m,ans;//n点数，m边数，ans连通块数量。
bool a[105][105],vis[105];//a邻接矩阵，vis标记。
void dfs(int x){
for(int i=1;i<=n;i++){
if(a[x][i]&&!vis[i]){
vis[i]=1;
dfs(i);
}
}
}//遍历。
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=0;
}
}//初始化邻接矩阵。
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
a[u][v]=1;
a[v][u]=1;
}//输入邻接矩阵。
for(int i=1;i<=n;i++){
if(!vis[i])dfs(i),ans++;
}
cout<<ans;//输出数量。
}这道题讲完了，作者正摆烂着度过一个漫长无聊的寒假，非常不容易，留下你的点赞再走吧！文章来源地址https://www.toymoban.com/news/detail-644054.html
到了这里，关于C++ 图论之求图的连通块数量（邻接矩阵版）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
