首页 > 代码库 > Sicily connect components in undirected graph
Sicily connect components in undirected graph
题目介绍：
输入一个简单无向图，求出图中连通块的数目。
Input
输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=1000，0<=m<=10000。
以下m行，每行是一个数对v y，表示存在边(v,y)。顶点编号从1开始。
Output
单独一行输出连通块的数目。
Sample Input
5 31 21 32 4
Sample Output
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 }
Sicily connect components in undirected graph
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。