Kruskal算法

题目链接：https://www.acwing.com/problem/content/861/

题目描述

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入描述

第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出描述

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
1≤n≤105
1≤m≤2∗105
图中涉及边的边权的绝对值均不超过 1000

示例

输入

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出

6

Kruskal算法

算法介绍

一个有 n 个结点的连通图的最小生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

Kruskal算法是求最小生成树的经典算法，时间复杂度为O(mlogm)。

算法过程

Kruskal算法的基本思想是以边为主导地位，始终选择当前可用的最小边权的边（可以直接快排或者algorithm的sort）。每次选择边权最小的边链接两个端点是kruskal的规则，并实时判断两个点之间有没有间接联通。具体见代码。

AC代码

---

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

#define INF 0x3f3f3f3f

using namespace std;

struct Edge
{
	int a, b, c;
	bool operator<(const Edge &t)
	{
		return this->c < t.c;
	}
};

const int N = 1e5 + 10;
const int M = 2e5 + 10;
int n, m;
int p[N];
Edge edge[M];

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++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edge[i] = {a, b, c};
	}
	sort(edge, edge + m);
	for (int i = 1; i <= n; i++)
		p[i] = i;
	int res = 0, cnt = 0;   //cnt记录生成树的边数
	for (int i = 0; i < m; i++)
	{
		int a = edge[i].a, b = edge[i].b, c = edge[i].c;
		a = find(a);
		b = find(b);
		if (a != b)
		{
			p[a] = b;
			res += c;
			cnt++;
		}
	}
	if (cnt < n - 1)    //小于n-1条说明这不是连通图
		cout << "impossible" << endl;
	else
		cout << res << endl;
	return 0;
}