#include <stdio.h> #include <vector> #include <algorithm> struct node { node* parent; int rank; // For the union-by-rank heuristic int n; // Number of this node node() : parent(this), rank(0) { } }; struct edge { node* a, *b; int weight; edge(node* a, node* b, int weight) : a(a), b(b), weight(weight) {} }; void link(node* a, node* b) // Disjoint set union { if(a->rank > b->rank) b->parent = a; else { a->parent = b; if(a->rank == b->rank) b->rank++; } } node* find(node* s) // Disjoint set find { if(s != s->parent) s->parent = find(s->parent); return s->parent; } void join(node* a, node* b) { link(find(a), find(b)); } std::vector<node> nodes; std::vector<edge> edges; std::vector<edge*> ans; int main() { int N, M; scanf("%d %d", &N, &M); nodes.reserve(N+1); for(int i = 0; i < N+1; i++) { nodes.push_back(node()); nodes.back().parent = &nodes.back(); nodes.back().n = i; } edges.reserve(M); ans.reserve(M); for(int i = 0; i < M; i++) { int x, y, w; scanf("%d %d %d", &x, &y, &w); edges.emplace_back(&nodes[x], &nodes[y], w); } std::sort(edges.begin(), edges.end(), [] (edge& a, edge& b) { return a.weight < b.weight; }); int max = 0; for(edge& e : edges) { if(find(e.a) != find(e.b)) { join(e.a, e.b); max = std::max(max, e.weight); ans.push_back(&e); } } printf("%d\n", max); printf("%d\n", ans.size()); for(auto e : ans) printf("%d %d\n", e->a->n, e->b->n); return 0; }解释算法
时间: 2024-04-28 11:23:18 浏览: 11
这段代码实现了Kruskal算法,用于求解最小生成树问题。Kruskal算法通过不断加入边,使得生成树中的边权值之和最小,直到生成树中包含了所有的节点。
算法的核心是使用不相交集合数据结构来维护生成树中的连通性。代码中定义了一个`node`结构体,表示图中的一个节点,其中`parent`指向该节点所在的集合的代表节点,`rank`表示该集合的秩(即树的深度),`n`表示该节点的编号。`edge`结构体表示两个节点之间的边,其中`a`和`b`指向这两个节点,`weight`表示边的权值。
代码中,首先读入图的节点数和边数,然后按照输入顺序创建所有的节点,并将它们初始化为不同的集合。接着读入所有的边,并将它们按照权值从小到大排序。遍历排序后的边,对于每条边,如果它所连接的两个节点不在同一个集合中,则将它们加入同一个集合,并将该边加入最小生成树的边集中。最后输出最小生成树的边权值之和和所有的边。
这段代码的时间复杂度为O(MlogM),其中M为边数。因为排序是最耗时的部分,所以算法的时间复杂度主要取决于排序的时间复杂度。
相关问题
#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct LNode { ElemType da
`#include <stdio.h>`和`#include <stdlib.h>`是C语言中的两个头文件。`<stdio.h>`是标准输入输出头文件,提供了一些用于输入输出的函数和宏定义。`<stdlib.h>`是标准库头文件,提供了一些常用的函数和宏定义,如内存分配、随机数生成等。
在你的代码中,`typedef int ElemType;`定义了一个类型别名,将`int`类型命名为`ElemType`。
`typedef struct LNode`定义了一个结构体类型`LNode`,结构体是一种自定义的数据类型,可以包含多个不同类型的成员变量。在这里,`LNode`结构体中的成员变量还没有完整定义,因此代码截断了。
编写C语言代码,将.c文件中的#include<stdio.h>展开
以下是一个简单的C语言代码,用于将.c文件中的#include<stdio.h>展开:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void expand_header(const char* filename) {
FILE* fp = fopen(filename, "r");
if (fp == NULL) {
printf("Failed to open file!\n");
return;
}
// 创建一个新的临时文件
char* tmp_filename = strdup("tmp.c");
FILE* tmp_fp = fopen(tmp_filename, "w");
// 逐行读取输入文件
char line[1024];
while (fgets(line, sizeof(line), fp)) {
// 检查是否包含#include<stdio.h>
if (strstr(line, "#include<stdio.h>") != NULL) {
// 打开stdio.h文件并将其内容复制到临时文件中
FILE* stdio_fp = fopen("stdio.h", "r");
if (stdio_fp != NULL) {
char stdio_line[1024];
while (fgets(stdio_line, sizeof(stdio_line), stdio_fp)) {
fputs(stdio_line, tmp_fp);
}
fclose(stdio_fp);
}
} else {
// 将当前行复制到临时文件中
fputs(line, tmp_fp);
}
}
// 关闭文件并删除原来的文件
fclose(fp);
remove(filename);
// 将临时文件重命名为原来的文件名
rename(tmp_filename, filename);
// 释放内存
free(tmp_filename);
fclose(tmp_fp);
}
int main() {
const char* filename = "test.c";
expand_header(filename);
printf("Header expanded successfully!\n");
return 0;
}
```
请注意,此代码只是一个简单的示例,仅展开了一个#include<stdio.h>语句,而且还假设stdio.h文件位于当前目录中。在实际情况中,可能需要展开多个#include语句,并且可能需要处理一些特殊情况,例如条件编译指令。此外,展开头文件可能会导致代码变得冗长和难以阅读,因此在实际项目中,应该尽量避免手动展开头文件。