Algorithms: Design and Analysis, Part 2: Week 2, Problem 1

clustering.cpp

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_V = 100000;
const int MAX_E = 1000000;
typedef long long ll;

//UF
int par[MAX_V];
int rank[MAX_V];
void init_union_find( int n ) {
    for( int i = 0; i < n; ++i ) {
        par[i] = i;
        rank[i] = 0;
    }
}

int find( int x ) {
    while( x != par[x] ) {
        par[x] = par[par[x]];
        x = par[x];
    }

    return x;
}

void unite( int x, int y ) {
    x = find( x );
    y = find( y );

    if( x == y ) return ;

    if( rank[x] < rank[y] ) {
        par[x] = y;
    } else {
        par[y] = x;

        if( rank[x] == rank[y] ) ++rank[x];
    }
}

bool same( int x, int y ) {
    return find( x ) == find( y );
}

//Graph
struct Edge {
    int u, v, cost;
    Edge( int _u = 0, int _v = 0, int _cost = 0 ): u( _u ), v( _v ), cost( _cost ) {}
};

bool cmp( const Edge &e1, const Edge &e2 ) {
    return e1.cost < e2.cost;
}


Edge es[MAX_E];
int V, E;

void clustering( int _k ) {
    int cluster = V;
    int k = _k;
    sort( es, es + E, cmp );
    init_union_find( V );
    ll sum_of_weight = 0;

    for( int i = 0; i < E; ++i ) {
        Edge &e = es[i];

        if( !same( e.u, e.v ) ) {
            unite( e.u, e.v );
            sum_of_weight += e.cost;
            --cluster;

            if( cluster == k - 1 ) {
                printf( "%d\n", e.cost );
                break;
            }
        }
    }

    //printf( "%lld\n", sum_of_weight );
}

int main( void ) {
    freopen( "clustering1.txt", "r", stdin );
    int cases = 1;
    //scanf( "%d", &cases );

    while( cases-- ) {
        scanf( "%d", &V );
        int a, b, w;
        int i = 0;

        while( scanf( "%d %d %d", &a, &b, &w ) != EOF ) {
            Edge e( a - 1, b - 1, w );
            es[i++] = e;
        }

        E = i;
        clustering( 4 );
    }

    return 0;
}