生成樹算法的一個(gè)應(yīng)用
#include <stdio.h>

#include <stdlib.h>

int city[2005];

void make ( int n )
{

    for ( int i=0; i<n; i++ )
    {
        city[i] = -1;
    }
}

int find ( int a )
{

    if ( city[a] < 0 )
    {
        return a;
    }
    int root = find ( city[a] );
    city[a] = root;

    return root;
}

void un ( int a, int b )
{

    int ra = find ( a );
    int rb = find ( b );

    if ( city[ra] < city[rb] )
    {
        city[ra] += city[rb];
        city[rb] = ra;
    }
    else
    {
        city[rb] += city[ra];
        city[ra] = rb;
    }
}

typedef struct
{
    int b;
    int e;
    int len;
}type;
type seg[10005];

int cmp ( const void *a, const void *b )
{

    return ( ( type * )a )->len - ( ( type * )b )->len;
}

int main ()
{

    int n, m;
    int a, b, l;

    while ( scanf ( "%d%d", &n, &m ) != EOF )
    {

        for ( int i=0; i<m; i++ )
        {
            scanf ( "%d%d%d", &a, &b, &l );
            seg[i].b = a - 1;
            seg[i].e = b - 1;
            seg[i].len = l;
        }
        qsort ( seg, m, sizeof ( type ), cmp );

        int max = -1;
        make ( n );
        for ( i=0; i<m; i++ )
        {
            if ( find ( seg[i].b ) != find ( seg[i].e ) )
            {
                if ( max < seg[i].len )
                {
                    max = seg[i].len;
                }
                un ( seg[i].b, seg[i].e );
            }
        }

        printf ( "%d\n", max );
    }
    return 0;
}