算法笔记：最小生成树

摸鱼摸了一个算法，打开书，看了一下感觉其中一个算法就是并查集的缩水版.. （但是我看了半天并没有看出这个算法用在哪些地方）

描述

给定一张边带权的无向图(G=（V,E）,n = |V|, m = |E|) 由(V)中全部(n)个定点和(E)中(n-1)条边构成的无向联通子图被称作(G)的一棵生成树。边的权值之和最小的生成树被称为无向图(G)的最小生成树（MST）

定理

任意一棵最小生成树一定包含无向图中权值最小的边

Kruskal算法

Kruskal在任何时刻，总是从剩余的边中选出一条权值最小的，而且这条边的两个端点属于生成森林中的两棵不同的树（不连通），将该边加入生成森林。

题目讲解

因为这个题目就是板子所以我就直接发就好了~~（偷懒逃..）~~

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

输入格式：

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式：

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

输入样例#1：

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

输出样例#1：

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=20

对于40%的数据：N<=50，M<=2500

对于70%的数据：N<=500，M<=10000

对于100%的数据：N<=5000，M<=200000

扔代码

//#define fre yes

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 500010;
struct Node{
    int x,y,z;
}edge[maxn];

int par[maxn];
int n,m,ans,tot;

template<typename T>inline void read(T&x)
{
    x = 0;char c;int lenp = 1;
    do { c = getchar();if(c == '-') lenp = -1; } while(!isdigit(c));
    do { x = x * 10 + c - '0';c = getchar(); } while(isdigit(c));
    x *= lenp;
}

bool cmp (Node x,Node y)
{
    return x.z < y.z;
}

int find(int x)
{
    if(par[x] == x) return x;
    else return par[x] = find(par[x]);
}

int main()
{
    read(n);read(m);
    for (int i=1;i<=m;i++)
    {
        int x,y,z;
        read(x);read(y);read(z);
        edge[i].x = x;
        edge[i].y = y;
        edge[i].z = z;
    } sort(edge+1,edge+1+m,cmp);
    for (int i=1;i<=n;i++) par[i] = i;
    for (int i=1;i<=m;i++)
    {
        int x = find(edge[i].x);
        int y = find(edge[i].y);
        if(x == y) continue;

        tot++;
        par[x] = y;
        ans += edge[i].z;
    } if(tot < n-1) puts("orz");
    else printf("%d
",ans);
    return 0;
}