UVa : 10199 (Tourist Guide)



// http://uva.onlinejudge.org/external/101/10199.html
// Tag: DFS, Articular point 
// Runtime: 0.026s

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


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

using namespace std;

int n;

map<string, int> cityIndex;

vector<int> matrix [100 + 5];

bool vis [100 + 5];
bool vis2 [100 + 5];

vector<string> output;

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

void checkHasCamera(int city)
{
    int cnt = 0;
    
    for ( int i = 0; i < n; i++ ) {
        if (vis [i] != vis2 [i]) cnt++;
    }
    
    // this 1 means, the city we discarded (i.e. its not an articular point)
    if (cnt == 1) return;
    
    for ( map<string, int>::iterator it = cityIndex.begin(); it != cityIndex.end(); it++ ) {
        if ((*it).second == city) {
            output.push_back((*it).first);
        }
    }
}

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

int main ()
{
    int cases = 0;
    
    bool blank = false;
    
    while (scanf ("%d", &n) && n) {
        
        char input [30 + 10];
        
        int index = 0;
        
        reset();
        
        for ( int i = 0; i < n; i++ ) {
            scanf ("%s", input);
            cityIndex [input] = index++;
        }
        
        int m;
        scanf ("%d", &m);
        
        char city1 [30 + 10];
        char city2 [30 + 10];
        
        for ( int i = 0; i < m; i++ ) {
            scanf ("%s %s", city1, city2);
            matrix [cityIndex [city1]].push_back(cityIndex [city2]);
            matrix [cityIndex [city2]].push_back(cityIndex [city1]);
        }
        
        for ( int i = 0; i < n; i++ ) {
            
            // lets discard "i" and see if it can be a camera point
            memset(vis, false, sizeof vis);
            
            // first, mark the connected graph that contains "i"
            dfs(i, -1, vis);

            for ( int j = 0; j < n; j++ ) {
                if (vis [j] && i != j) {
                    
                    // second, start with another city from the graph that contains "i"
                    // this time, we are going to discard "i"
                    
                    memset(vis2, false, sizeof vis2);
                    
                    dfs(j, i, vis2);
                    
                    checkHasCamera(i);
                    
                    break;
                }
            }
        }
        
        sort(output.begin(), output.end());
        
        if (blank) printf ("\n");
        blank = true;
        
        printf ("City map #%d: %d camera(s) found\n", ++cases, (int) output.size());
        
        for (int i = 0; i < output.size(); i++) {
            cout << output [i] << endl;
        }
    }
    
    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