给定几条边,需求出还需几条使节点连成无向连通图c++代码
时间: 2023-12-21 11:15:08 浏览: 22
以下是一个简单的 C++ 代码示例,使用 Kruskal 算法来计算需要添加的边数:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> parent;
int find(int i) {
if (parent[i] == i) {
return i;
}
return parent[i] = find(parent[i]);
}
void unionSet(int x, int y) {
parent[find(x)] = find(y);
}
int addEdgesToMakeConnected(int n, vector<vector<int>>& edges) {
// 初始化每个节点的父节点
parent.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int num_edges = edges.size();
for (int i = 0; i < num_edges; i++) {
int x = find(edges[i][0]);
int y = find(edges[i][1]);
if (x != y) {
unionSet(x, y);
}
}
// 计算需要添加的边数
int num_add_edges = 0;
for (int i = 0; i < n; i++) {
if (parent[i] == i) {
num_add_edges++;
}
}
return num_add_edges - 1;
}
int main() {
int n = 5;
vector<vector<int>> edges{{0, 1}, {1, 2}, {3, 4}};
int num_add_edges = addEdgesToMakeConnected(n, edges);
cout << num_add_edges << endl; // 输出 1,需要再添加一条边
return 0;
}
```
其中,参数 `n` 表示节点数,参数 `edges` 是一个二维数组,包含给定的边,每条边是一个由两个节点组成的数组。函数 `addEdgesToMakeConnected` 返回需要添加的边数,使所有节点连成一个无向连通图。