UVa : 796 (Critical Links)



// http://uva.onlinejudge.org/external/7/796.html
// Tag: Dfs, Articular Point
// Runtime: 0.356s

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


#include <cstdio>
#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <cstring>

#define N 100 + 5

using namespace std;

int n;

bool matrix [N] [N];

bool vis [N];
bool vis2 [N];

vector<string> output;

void dfs(int at, bool *v)
{
    v [at] = true;
    
    for ( int i = 0; i < n; i++ ) {
        if (matrix [at] [i] && !v [i]) {
            dfs (i, v);
        }
    }
}

void reset()
{
    memset(matrix, false, sizeof matrix);
    
    output.clear();
}

bool isCritical()
{
    for ( int i = 0; i < N; i++ )
        if (vis [i] != vis2 [i]) return true;
    
    return false;
}

int main ()
{
    while (scanf ("%d", &n) != EOF) {
        
        reset();
        
        for ( int i = 0; i < n; i++ ) {
            int a, b, c;
            scanf ("%d (%d)", &a, &b);
            
            for (int j = 0; j < b; j++ ) {
                scanf ("%d", &c);
                
                matrix [a] [c] = matrix [c] [a] = true;
            }
        }
        
        for ( int i = 0; i < n; i++ ) {
            for ( int j = i + 1; j < n; j++ ) {
                if (matrix [i] [j]) {
                    memset(vis, false, sizeof vis);
                    dfs(i, vis);
                    memset(vis2, false, sizeof vis2);
                    matrix [i] [j] = matrix [j] [i] = false;
                    dfs(i, vis2);
                    matrix [i] [j] = matrix [j] [i] = true;
                    if (isCritical()) {
                        char out [12];
                        sprintf (out, "%d - %d", i, j);
                        output.push_back(out);
                    }
                }
            }
        }
        
        printf ("%d critical links\n", (int) output.size());
        
        for ( int i = 0; i < output.size(); i++ ) {
            cout << output [i] << endl;
        }
        
        printf ("\n");
    }
    
    
    return 0;
}

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