[UVa] 10199 - Tourist Guide

The problem uses the concept of Articulation Points. One critical case is when the graph is already disconnected.
Method: For each vertex, I first counted it's child count (dfscount, dfsnum). Then I counted them again after disconnecting that vertex. If both of them aren't same, I incremented the Articulation Point count, because that vertex is an articulation point.

6
sugarloaf
maracana
copacabana
ipanema
corcovado
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
corcovado sugarloaf
lapa corcovado
5
guanabarabay
downtown
botanicgarden
colombo
sambodromo
4
guanabarabay sambodromo
downtown sambodromo
sambodromo botanicgarden
colombo sambodromo
6
a
b
d
c
e
f
7
a b
a d
d c
b d
c e
c f
e f
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f g
7
g
f
e
d
c
b
a
7
a b
b c
c d
d e
e f
f g
g a
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f a
6
a
b
c
d
e
f
5
a b
a f
c d
c e
d e
3
a
b
c
2
a b
b c
0

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


using namespace std;


bool visited[200], con[200][200];
int dfscounter;
int dfs(int v, int n) {
    visited[v] = true;
    dfscounter++;
    for (int i=1 ; i<=n ; i++) {
        if (!visited[i] && con[v][i]) {
            dfs(i, n);
        }
    }
}
map<string, int> cmap;
vector<string> lst;
int artP;
int main( ) {
    int n, e, kase=1;

    //freopen("tourist.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);

    while ( cin >> n ) {

        if (!n) break;

        if (kase>1) cout << endl;

        cmap.clear();
        lst.clear();
        artP = 0;
        for (int i=1 ; i<=n ; i++) {
            string a;
            cin >> a;
            cmap[a] = i;
        }
        cin >> e;
        for (int i=1 ; i<=n ; i++) for (int j=1 ; j<=n ; j++) con[i][j] = false;
        for (int i=1 ; i<=e ; i++) {
            string a, b;
            cin >> a >> b;
            con[ cmap[a] ][ cmap[b] ] = con[ cmap[b] ][ cmap[a] ] = true;
        }
        for (map<string, int>::iterator it=cmap.begin() ; it!=cmap.end() ; it++) {
            int rcount;
            dfscounter=0;
            for (int i=1 ; i<=n ; i++) visited[i] = false;
            dfs(it->second, n);
            rcount = dfscounter;
            for (int i=1 ; i<=n ; i++) visited[i] = false;
            visited[it->second] = true;
            dfscounter=0;
            for (int i=1 ; i<=n ; i++) {
                if (con[ it->second ][i]) {
                    dfs(i, n);
                    break;
                }
            }
            if (rcount>1 && dfscounter!=rcount-1) {
                artP++;
                lst.push_back(it->first);
            }
        }

        printf("City map #%d: %d camera(s) found\n",kase++,lst.size());
        for (int i=0 ; i<lst.size() ; i++) {
            cout << lst[i] << endl;
        }

    }

}