图深度优先搜索之block的个数

本文主要是介绍图深度优先搜索之block的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>
#include <cstring>
using namespace std;int path[1001][1001];
int visited[1001];
int n,m;//将与x相连的节点都标记为已访问 
void dfs(int x){visited[x] = 1; //标记x已访问的位置要正确，要先处理x已访问，不然会漏了一种情况 for(int i=1;i<=n;i++){if(!visited[i] && path[x][i] == 1){//visited[i] = 1;dfs(i);}}
}int main(){memset(path,0,sizeof(path));memset(visited,0,sizeof(visited));cin>>n>>m;for(int i=0;i<m;i++){int a,b;cin>>a>>b;path[a][b] = 1;path[b][a] = 1;}int block = 0;//遇到未访问的节点，block就加一，然后将与该节点相连的所有节点都标记为访问过 //Attention!!!!!!!!一定要注意节点的下标是从1开始的！！！！ for(int i=1;i<=n;i++){if(visited[i] == 0){block++;dfs(i);}}cout<<block<<endl;return 0;
}

这篇关于图深度优先搜索之block的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---