UVa : 11749 (Poor Trade Advisor)



// http://uva.onlinejudge.org/external/117/11749.html
// Tag: DFS
// Runtime: 0.482s

//
//  main.cpp
//  UVa
//
//  Created by Shahab Uddin.
//  Copyright (c) 2014 Shahab Uddin. All rights reserved.
//

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>

#define Inf 2147483648

using namespace std;

int n;

int matrix [500 + 5] [500 + 5];

int highestPPA;

bool visited [500 + 5];

set <int> thisComponent;

void dfs(int at)
{
    for ( int i = 1; i <= n; i++ ) {
        if (matrix [at] [i] == highestPPA && !visited [i]) {
            visited [at] = visited [i] = true;
            thisComponent.insert(at);
            thisComponent.insert(i);
            dfs(i);
        }
    }
}

void reset()
{
    for ( int i = 0; i < 505; i++ ) {
        for ( int j = 0; j < 505; j++ ) {
            matrix [i] [j] = -Inf;
        }
    }
}

int main ()
{
    int m;
    
    while (scanf ("%d %d", &n, &m) != EOF) {
        
        if (n == 0 && m == 0) break;
        
        highestPPA = -Inf;
        
        reset();
        
        for ( int i = 0; i < m; i++ ) {
            int a, b, c;
            scanf ("%d %d %d", &a, &b, &c);
            
            // multiple edges with different PPA, take the maximum one
            if (c > matrix [a] [b])
                matrix [a] [b] = matrix [b] [a] = c;
            
            highestPPA = max(highestPPA, c);
        }
        
        memset(visited, false, sizeof visited);
        
        int maxConnected = 0;
        
        for ( int i = 1; i <= n; i++ ) {
            if (!visited [i]) {
                thisComponent.clear();
                dfs(i);
                maxConnected = max (maxConnected, (int) thisComponent.size());
            }
        }
        
        printf ("%d\n", maxConnected);
    }
    
    return 0;
}

One thought on “UVa : 11749 (Poor Trade Advisor)

  1. The more I talked to normal people who had normal, healthy, loving relationships the more I could see the dysfunction of my own relationship. Fourth, be honest with yourself about what your weaknesses or intentions might be.

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