Sicily connect components in undirected graph

For study!

Posted by Winray on March 4, 2016
  • 题目介绍:
输入一个简单无向图,求出图中连通块的数目。

Input
输入的第一行包含两个整数n和m,n是图的顶点数,m是边数。1<=n<=1000,0<=m<=10000。

以下m行,每行是一个数对v y,表示存在边(v,y)。顶点编号从1开始。
Output
单独一行输出连通块的数目。

Sample Input
5 3
1 2
1 3
2 4
Sample Output
2
  • 思路:
    • 利用广度搜索,计算广度搜索的次数即为结果。
  • 具体代码如下:
#include <iostream>
#include <queue>
using namespace std;

bool path[1001][1001];
bool visited[1001];

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int node1, node2;
        cin >> node1 >> node2;
        path[node1][node2] = true;
        path[node2][node1] = true;
    }
    
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }
    
    int count = 0;
    int temp = n;
    while (temp--) {
        queue<int> store;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                store.push(i);
                count++;
                visited[i] = true;
                break;
            }
        }
        
        while (!store.empty()) {
            for (int i = 1; i <= n; i++) {
                if (path[store.front()][i] && !visited[i]) {
                    store.push(i);
                    visited[i] = true;
                }
            }
            store.pop();
        }
    }
    
    cout << count << endl;
    
    return 0;
}