UVa : 11857 (Driving Range)



// http://uva.onlinejudge.org/external/118/11857.html
// Runtime : 1.316s
// Tag : Dfs, Connected Graph, MST (Kruskal / Prim) 


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

struct EdgeInfo {
    int start;
    int end;
    int dist;
} a [N];

int parent [N];
bool vis [N];
vector <int> Edge [N];
int n, m;

void reset ()
{
    for ( int i = 0; i < n; i++ ) {
        vis [i] = false;
        Edge [i].clear ();
        parent [i] = i;
    }
}

void dfs (int u)
{
    vis [u] = true;

    for ( size_t i = 0; i < Edge [u].size (); i++ ) {
        if ( !vis [Edge [u] [i]] ) dfs (Edge [u] [i]);
    }
}

bool cmp (EdgeInfo x, EdgeInfo y)
{
    if ( x.dist < y.dist ) return true;
    return false;
}

int parentOf (int n)
{
    if ( n == parent [n] ) return n;
    return parent [n] = parentOf ( parent [n] );
}

int main ()
{
    while ( scanf ("%d %d", &n, &m) ) {
        if ( n == 0 && m == 0 ) break;

        reset ();

        for ( int i = 0; i < m; i++ ) {
            scanf ("%d %d %d", &a [i].start, &a [i].end, &a [i].dist);
            Edge [a [i].start].push_back (a [i].end);
            Edge [a [i].end].push_back (a [i].start);
        }

        dfs (0);

        bool impossible = false;

        for ( int i = 0; i < n; i++ ) {
            if ( !vis [i] ) { impossible = true; break; }
        }

        if (impossible) { printf ("IMPOSSIBLE\n"); continue; }

        sort (a, a + m, cmp);

        int maxRange = 0;
        int selectedEdges = m - 1;

        for ( int i = 0; i < m && selectedEdges; i++ ) {
            int p = parentOf (a [i].start);
            int q = parentOf (a [i].end);
            if ( p != q ) {
                parent [p] = q;
                selectedEdges--;
                if ( a [i].dist > maxRange ) maxRange = a [i].dist;
            }
        }

        printf ("%d\n", maxRange);
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s