两个拥有共同好友的人可以被认为属于同一个朋友圈。给定一个包含 N 个顶点 M 条边的无向图,其中每个顶点表示一个人,每条边表示两个人是朋友关系,请你判断这 N 个人中有几个不同的朋友圈。C++广搜实现
时间: 2024-10-29 08:11:01 浏览: 35
js-utils-给定两个字符串s和t
在图论中,这个问题通常被称为“连通组件”或“强连通分量”,因为我们需要找出所有互为朋友并且彼此之间可以直接通过朋友链连接的人组成的集合。如果每个人都恰好在一个大的朋友圈里,那么就有多少个这样的集合就代表有多少个不同的朋友圈。
解决此类问题的一个常见算法是深度优先搜索(DFS)或广度优先搜索(BFS),因为它们都可以用来查找图中的连通分量。这里我们使用广度优先搜索更为合适,因为无向图的连通分量通常是树形结构或者是树形结构的并集,而BFS能保证先找到距离起点较近的部分。
以下是使用C++实现广度优先搜索的基本步骤:
1. 创建一个布尔数组`visited`来标记每个节点是否已经访问过,初始全部设为`false`。
2. 定义一个vector用于存储当前朋友圈的顶点集合,初始化为一个空集合。
3. 对于每一个未访问过的节点,从任意一个节点开始(比如选择一个顶点作为起始节点`start`),然后进行BFS遍历:
a. 将该节点加入当前朋友圈集合,并将其标记为已访问。
b. 对于该节点的所有邻居,如果邻居还没有被访问过,将邻居加入当前集合并继续遍历邻居的邻居,直到遍历完所有邻居为止。
4. 遍历结束后,统计`visited`数组中为`true`的元素数量,即为不同的朋友圈的数量。
```cpp
#include <iostream>
#include <vector>
using namespace std;
void bfs(vector<vector<int>>& graph, vector<bool>& visited, int& count) {
// 初始化访问标志和朋友圈计数
for (int i = 0; i < graph.size(); ++i)
visited[i] = false;
// 从任意未访问节点开始遍历
count = 0;
for (int start = 0; start < graph.size(); ++start) {
if (!visited[start]) {
count++;
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
// 添加邻居到当前朋友圈
for (auto neighbor : graph[node])
if (!visited[neighbor])
q.push(neighbor), visited[neighbor] = true;
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>());
// 根据输入构建图
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u); // 因为图是无向的
}
vector<bool> visited(n);
int num_communities = 0;
bfs(graph, visited, num_communities);
cout << "有 " << num_communities << " 个不同的朋友圈." << endl;
return 0;
}
```
阅读全文