如何使用c++,保证只有四个点,如果大于四个点,将相邻的点合并成一点
时间: 2023-05-18 07:06:04 浏览: 44
这可以使用 Kruskal 算法来实现。首先将所有的点看作一个独立的集合,然后按照边的权值从小到大进行排序。接着依次选择每一条边,如果这条边连接的两个点不在同一个集合中,就将它们合并成一个集合,直到只剩下四个点为止。这样就可以保证只有四个点,并且相邻的点会被合并成一个点。以下是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
#define MAX_EDGES 100
typedef struct {
int u, v, w;
} Edge;
int parent[MAX_VERTICES];
int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
parent[find(x)] = find(y);
}
int cmp(const void *a, const void *b) {
return ((Edge *)a)->w - ((Edge *)b)->w;
}
int main() {
int n, m, i, j, k;
Edge edges[MAX_EDGES];
scanf("%d%d", &n, &m);
for (i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
}
for (i = 1; i <= n; i++) {
parent[i] = i;
}
qsort(edges, m, sizeof(Edge), cmp);
for (i = 0, j = 0, k = n; k > 4; i++) {
if (find(edges[i].u) != find(edges[i].v)) {
merge(edges[i].u, edges[i].v);
k--;
if (j < 3 && edges[i].w > 0) {
printf("%d ", edges[i].w);
j++;
}
}
}
return 0;
}
```
这段代码使用了并查集来维护集合,使用了 Kruskal 算法来求最小生成树,并且在输出最小生成树的边时只输出了前三条非零边。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)