acwing算法基础之搜索与图论--kruskal算法

1 基础知识

kruskal算法的关键步骤为：

1. 将所有边按照权重从小到大排序。
2. 定义集合S，表示生成树。
3. 枚举每条边(a,b,c)，起点a，终点b，边长c。如果结点a和结点b不连通（用并查集来维护），则将这条边加入到集合S中。

kruskal算法的时间复杂度为O(mlogm)，它用来解决稀疏图的最小生成树问题。

2 模板

int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组struct Edge     // 存储边
{int a, b, w;bool operator< (const Edge &W)const{return w < W.w;}
}edges[M];int find(int x)     // 并查集核心操作
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int kruskal()
{sort(edges, edges + m);for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集int res = 0, cnt = 0;for (int i = 0; i < m; i ++ ){int a = edges[i].a, b = edges[i].b, w = edges[i].w;a = find(a), b = find(b);if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并{p[a] = b;res += w;cnt ++ ;}}if (cnt < n - 1) return INF;return res;
}

3 工程化

题目1：求最小生成树。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 2e5 + 10;
int p[N];
int n, m;struct Edge {int a, b, w;bool operator< (const Edge& W) const {return w < W.w;}
}edges[N];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {cin >> n >> m;for (int i = 0; i < m; ++i) {cin >> edges[i].a >> edges[i].b >> edges[i].w;}//初始化并查集for (int i = 1; i <= n; ++i) p[i] = i;sort(edges, edges + m);int res = 0, cnt = 0;for (int i = 0; i < m; ++i) {int a = edges[i].a, b = edges[i].b, w = edges[i].w;a = find(a);b = find(b);if (a != b) {p[a] = b;res += w;cnt ++;}}if (cnt < n-1) {cout << "impossible" << endl;} else {cout << res << endl;}return 0;
}