---
# System prepended metadata

title: Kruskal
tags: [Algorithm]

---

Kruskal
===
###### tags: `Algorithm`
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
#define maxE 10000
#define maxN 110

// given
int n, e;
int to[maxE], from[maxE], w[maxE], id[maxE];
inline bool cmp( int a, int b)
{
    return w[a]<w[b];
}

// disjointed set
int p[maxN];
int find( int x)
{
    return (p[x]==x) ? (x) : (p[x]=find(p[x]));
}
inline void uni( int a, int b)
{
    p[find(a)] = find(b);
}
inline void init()
{
    for( int i=1; i<=n; i++)
    {
        p[i] = i;
    }
}

long long MST()
{
    long long wsum = 0;
    init();
    sort( id, id+e, cmp);

    for( int i=0; i<e; i++)
    {
        int &a=to[id[i]], &b=from[id[i]];
        if (find(a)==find(b)) continue;

        uni(a,b);
        wsum += w[id[i]];
    }

    return wsum;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    while (cin>>n)
    {
        if (n==0) return 0;

        e = n*(n-1) >> 1;
        for( int i=0; i<e; i++)
        {
            cin >> from[i] >> to[i] >> w[i];
            id[i] = i;
        }

        cout << MST() << '\n';
    }
}
```