題目描述：

輸入一個簡單無向圖，求出圖中連通塊的數目

輸入：

?

輸入的第一行包含兩個整數n和m，n是圖的頂點數，m是邊數。1<=n<=1000，0<=m<=10000。

以下m行，每行是一個數對v y，表示存在邊(v,y)。頂點編號從1開始。

?

題目分析：

利用深度優先搜索尋找連通塊數，一趟深度優先搜索為一個連通塊，深度優先搜索次數為塊數。

?

#include<iostream> #include<memory> using namespace std;const int MAX=1001; int edge[MAX][MAX]; int n, m; int num=0; bool isvisited[MAX];void DFS(int current) {for(int i=1;i<=n;i++){if(!isvisited[i]&&edge[current][i]){isvisited[i]=true;DFS(i);}} }int main() {cin>>n>>m;int a, b;//初始化 memset(edge, 0,sizeof(edge));memset(isvisited, false, sizeof(isvisited));for(int i=0;i<m;i++){cin>>a>>b;edge[a][b]=1;edge[b][a]=1;}for(int i=1;i<=n;i++){if(!isvisited[i]){num++;isvisited[i]=true;DFS(i);}}cout<<num<<endl;return 0; }

　　

轉載于:https://www.cnblogs.com/KennyRom/p/6243859.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的[SOJ] connect components in undirected graph的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。