UVa: 315 (Network)


  1. turn off each node, one at a time and run dfs from another node.
  2. after dfs check every node. if any node is not visited and its not the node that was turned off then criticalPlaces++

// http://uva.onlinejudge.org/external/3/315.html
// Runtime: 0.044s
// Tag: Dfs

// @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 long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

vector <int> v [100 + 5];
bool vis [100 + 5];
int n;

void reset ()
{
    for ( int i = 0; i < 105; i++ ) v [i].clear ();
}

int isCritical (int off)
{
    for ( int i = 1; i <= n; i++ ) {
        if ( vis [i] == false && i != off ) return 1;
    }

    return 0;
}

void dfs (int at, int off)
{
    vis [at] = true;

    for ( size_t i = 0; i < v [at].size (); i++ ) {
    	int a = v [at] [i];
    	//cout << a << endl;
        if ( vis [a] == false && a != off )
        	dfs (a, off);
    }
}

int main ()
{
    while ( scanf ("%d", &n) && n ) {
        getchar ();
        char input [10000];

        reset ();

        while ( gets (input) && strcmp (input, "0")) {
            char *pch;
            pch = strtok (input, " ");

            int node = atoi (pch);
            pch = strtok (NULL, " ");

            while ( pch != NULL ) {
                int conn = atoi (pch);
                v [node].push_back (conn);
                v [conn].push_back (node);
                pch = strtok (NULL, " ");
            }
        }

        if ( n == 1 ) { printf ("0\n"); continue; }

        int criticalPlaces = 0;

        Set (vis, false);
        dfs (2, 1);
        criticalPlaces += isCritical (1);

        for ( int i = 2; i <= n; i++ ) {
            Set (vis, false);
            dfs (1, i);
            criticalPlaces += isCritical (i);
        }

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

// @END_OF_SOURCE_CODE
Advertisements

One thought on “UVa: 315 (Network)

  1. i solved this problem using articulation point concept
    although it was nice to see your code as it used easier algorithm (dfs) for finding no of articulation points

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