Sicily Connect components in undirected graph

本文主要是介绍Sicily Connect components in undirected graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Source:

http://soj.sysu.edu.cn/show_problem.php?pid=1002&cid=2104

Description

输入一个简单无向图，求出图中连通块的数目。

Sample Input

输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=1000，0<=m<=10000。
以下m行，每行是一个数对v y，表示存在边(v,y)。顶点编号从1开始。

5 3
1 2
1 3
2 4

Sample Output

单独一行输出连通块的数目。

2

Caution:

水题，bfs之。

示例代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include <vector>using namespace std;int n, m, v, y,ans;
vector<int> g[10001];
int vis[10001];void init()
{cin >> n >> m;while (m--){cin >> v >> y;g[v].push_back(y);g[y].push_back(v);}
}void bfs(int s)
{vis[s] = 1;queue<int> q;q.push(s);while (!q.empty()){int u = q.front();for (int i = 0; i < g[u].size(); ++i)if (!vis[g[u][i]]){q.push(g[u][i]);vis[g[u][i]] = 1;}q.pop();}
}void solve()
{for (int i = 1; i <= n; ++i){if (vis[i] != 1){++ans;bfs(i);}}cout << ans << endl;
}int main()
{init();solve();return 0;
}

这篇关于Sicily Connect components in undirected graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---