最小生成树kruskal

彼岸朱砂 · 2019-01-25 20:42:12 · 个人记录

#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=500;
int n,m,root[N];
struct node
{
    int x,y,z;
}a[N];
int find(int x)
{
    if(x==root[x]) return x;
    else return find(root[x]);
}
bool comp(node s,node t)
{
    return s.z<t.z;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) root[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].z;
    }
    sort(a+1,a+1+m,comp);
    for(int i=1;i<=m;i++)
    {
        int fx=find(a[i].x);
        int fy=find(a[i].y);

        if(fx!=fy) 
        {
            root[fy]=fx;    
            cout<<a[i].x<<"->"<<a[i].y<<endl;
        }
    }
    return 0;
}

样例： 4 5

1 2 1

1 3 2

3 4 2

2 4 2

1 4 2

答案：

1->2

1->3

3->4