Sicily connect components in undirected graph，sicilyundirected

Sicily connect components in undirected graph，sicilyundirected

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

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

單獨一行輸出連通塊的數目。

5 3
1 2
1 3
2 4

2

思路：

     利用廣度搜索，計算廣度搜索的次數即為結果。

     具體代碼如下：

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 
 5 bool path[1001][1001];
 6 bool visited[1001];
 7 
 8 int main() {
 9     int n, m;
10     cin >> n >> m;
11     
12     for (int i = 0; i < m; i++) {
13         int node1, node2;
14         cin >> node1 >> node2;
15         path[node1][node2] = true;
16         path[node2][node1] = true;
17     }
18     
19     for (int i = 1; i <= n; i++) {
20         visited[i] = false;
21     }
22     
23     int count = 0;
24     int temp = n;
25     while (temp--) {
26         queue<int> store;
27         for (int i = 1; i <= n; i++) {
28             if (!visited[i]) {
29                 store.push(i);
30                 count++;
31                 visited[i] = true;
32                 break;
33             }
34         }
35         
36         while (!store.empty()) {
37             for (int i = 1; i <= n; i++) {
38                 if (path[store.front()][i] && !visited[i]) {
39                     store.push(i);
40                     visited[i] = true;
41                 }
42             }
43             store.pop();
44         }
45     }
46     
47     cout << count << endl;
48     
49     return 0;
50 }