[POJ] 1861 Network.cpp

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge{
    int A;
    int B;
    int Len;
}E[15001];
int Set[1001];

bool cmp(const Edge &A, const Edge &B);
void Set_Initial(const int &N);
int Find_Root(const int &x);
bool Union(const Edge &E);

int main()
{
    int N, M, A, B, L;
    while (scanf("%d %d", &N, &M) == 2) {

        for (int i = 0; i < M; ++i)
            scanf("%d %d %d", &E[i].A, &E[i].B, &E[i].Len);
        sort(E, E + M, cmp);
        Set_Initial(N);

        vector<Edge> Ans;
        for (int i = 0, currentEdge = 0; currentEdge != N - 1; ++i)
            if (Union(E[i])){
                ++currentEdge;
                Ans.push_back(E[i]);
            }
        printf("%d\n", (Ans.end()-1)->Len);
        printf("%d\n", Ans.size());
        for (int i = 0; i < Ans.size(); ++i)
            printf("%d %d\n", Ans[i].A, Ans[i].B);
    }
}
bool cmp(const Edge &A, const Edge &B) {
    return A.Len < B.Len;
}
void Set_Initial(const int &N)
{
    for (int i = 1; i <= N; ++i)
        Set[i] = i;
}
int Find_Root(const int &x)
{
    if (x == Set[x])
        return x;
    return Set[x] = Find_Root(Set[x]);
}
bool Union(const Edge &E)
{
    int x = Find_Root(E.A);
    int y = Find_Root(E.B);

    if (x != y) {
        Set[x] = y;
        return true;
    }
    return false;
}