联通块组件
2025-01-22 09:37:22
发布于：上海
19阅读
0回复
0点赞
邻接矩阵存图 DFS搜素连通块
#include<bits/stdc++.h>
using namespace std;
int n;//顶点数量
int m;//边数量
//二维矩阵存图
bool g[110][110]; //map表示我们从 i - > j是否有一条边 map[i][j]==true
bool vis[110];
void dfs(int u){
for(int i=1;i<=n;i++){
if(u==i)continue;//等于他本身
if(g[u][i] && !vis[i]){
vis[i] = true;
dfs(i);
}
}
}
int main(){
cin>>n>>m;
//双向边
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
g[u][v] = g[v][u] = true;
}
int cnt = 0;
for(int i=1;i<=n;i++){
if(vis[i])continue;
vis[i]=true;
dfs(i);
cnt++;
}
cout<<cnt;
return 0;
}
邻接表存图 DFS搜素连通块
#include<bits/stdc++.h>
using namespace std;
int n;//顶点数量
int m;//边数量
//邻接表
vector<int> g[110];
bool vis[110];
void dfs(int u){
for(int x:g[u]){
if(!vis[x]){
vis[x]=true;
dfs(x);
}
}
}
int main(){
cin>>n>>m;
//双向边
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
int cnt = 0;
for(int i=1;i<=n;i++){
if(vis[i])continue;
vis[i]=true;
dfs(i);
cnt++;
}
cout<<cnt;
return 0;
}
这里空空如也
有帮助，赞一个