[UVa] 796 - Critical Links

Method: The core idea is behind the DFS. It uses the d[u] data. low[u] contains the index of the topmost and leftmost vertex in the tree that u resides in. It is updated in two conditions. They are
1. If a vertex that is connected with u was visited earlier has a lower d[v] (d[v] is checked because u is part of v's tree then it's low[v] is still not reliable but d[v] is it's most reliable data)
2. If a fresh vertex is visited through u, then u can use that low[v] data and update itself in case v has a higher hierarchy access.
3. If low[v] > d[u], the explanation of this is that low[v] was generated during a traversal from v. During that traversal v could not find any other edge to reach u or any of it's preceding nodes. So, to reach the tree that u resides in, v must use the edge [u,v] which makes it a bridge essentially.

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
bool visited[200];
int d[200], low[200], brcount, br[200][200];
vector<int> g[200];
int dfs(int u, int parent, int depth) {
    visited[u] = true;
    d[u] = low[u] = depth;

    for (int i=0 ; i<g[u].size() ; i++) {
        int v = g[u][i];

        if (visited[v] && v!=parent) {
            low[u] = (low[u]<d[v]?low[u]:d[v]);
        }
        if (!visited[v]) {
            dfs(v, u, depth+1);
            low[u] = (low[u]<low[v]?low[u]:low[v]);
            if (low[v]>d[u]) {
                brcount++;
                br[u][v] = br[v][u] = true;
            }
        }
    }

}


int main( void ) {

    //freopen("brg.txt","r+",stdin);

    int n, v, x, e;

    while (~scanf("%d",&n)) {

        for (int i=0 ; i<200 ; i++) {
            g[i].clear();
            visited[i] = false;
            for (int j=0 ; j<200 ; j++) {
                br[i][j] = false;
            }
        }

        for (int i=0 ; i<n ; i++) {
            scanf("%d (%d)",&v,&e);
            for (int j=0 ; j<e ; j++) {
                scanf("%d",&x);
                g[v].push_back(x);
                g[x].push_back(v);
            }
        }

        brcount = 0;

        for (int i=0 ; i<n ; i++) {
            if (!visited[i]) {
                dfs(i, 0, 0);
            }
        }

        printf("%d critical links\n",brcount);
        for (int i=0 ; i<n ; i++) {
            for (int j=i+1 ; j<n ; j++) {
                if (br[i][j]) {
                    printf("%d - %d\n",i,j);
                    br[i][j] = br[j][i] = false;
                }
            }
        }
        printf("\n");
    }

    return 0;
}

[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;
        }

    }

}

[UVa] 315 - Network

#Articulation Points #Graph #DFS #BFS
Method:
Turn off each node and see if all the other nodes except that are visited or not using DFS
Sample I/O:

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
5
1 2
2 3 4
4 5
0
0

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool con[200][200];
vector< pair<int, int> > edges;
bool visit[200];

void init_con(int n) {
    for (int i=0 ; i<=n ; i++)
        for (int j=0 ; j<=n ; j++)
            con[i][j] = false;
}

int dfs_visit(int s, int n) {

    int vCount = 1;

    if (visit[s]) return 0;
    visit[s] = true;

    for (int i=1 ; i<=n ; i++) {
        if (!visit[i] && con[s][i]) {
            vCount += (dfs_visit(i,n));
        }
    }
    return vCount;
}

int dfs(int s, int n) {

    int vCount = 0;

    for (int i=1 ; i<=n ; i++) {
        visit[i] = false;
    }
    visit[s] = true;

    for (int i=1 ; i<=n ; i++) {
        if (!visit[i]) {
            vCount = dfs_visit(i,n);

            return vCount;
        }
    }
    return vCount;
}

int find_bridges(int n) {
    int aps = 0, i, j;


    for (int i=1  ; i<=n ; i++) {
        if (dfs(i,n) != (n-1)) aps++;
    }


    return aps;
}
char buf[10000];
int main( void ) {


    //freopen("inp.dat","r+",stdin);

    int n, result, vtx, plc;
    char *p;

    while (scanf("%d",&n)==1 && n!=0) {
        getchar();

        init_con(n);
        edges.clear();

        while (gets(buf)) {
            if (!strcmp(buf,"0")) break;
            p = strtok(buf," ");
            sscanf(p,"%d",&plc);

            while ((p=strtok(NULL," "))) {
                sscanf(p,"%d",&vtx);

                con[plc][vtx] = con[vtx][plc] = true;
                edges.push_back(make_pair(plc,vtx));
            }
        }

        result = find_bridges(n);

        cout << result << endl;
    }


    return 0;
}

[UVa] 784 - Maze Exploration

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int dirs[10][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

char maze[100][100];
int color[100][100];

void dfs_visit(int x, int y)
{
    int i;
    color[x][y]=2;
    maze[x][y]='#';
    for (i=0 ; i<8 ; i++)
    {
        if (color[x+dirs[i][0]][y+dirs[i][1]]==0 && maze[x+dirs[i][0]][y+dirs[i][1]]!='X' && maze[x+dirs[i][0]][y+dirs[i][1]]!='#')
            dfs_visit(x+dirs[i][0],y+dirs[i][1]);
    }
}

void dfs(int x, int y, int mh, int mw)
{
    int i, j;
    for (i=0 ; i<mh ; i++)
        for (j=0 ; j<mw ; j++)
            color[i][j] = 0;

    for (i=0 ; i<8 ; i++)
    {
        if (color[x+dirs[i][0]][y+dirs[i][1]]==0 && maze[x+dirs[i][0]][y+dirs[i][1]]!='X' && maze[x+dirs[i][0]][y+dirs[i][1]]!='#')
            dfs_visit(x+dirs[i][0],y+dirs[i][1]);
    }
}


int end(char *p)
{
    int i;
    for (i=0 ; p[i] ; i++)
    {
        if (p[i]!='_') return 0;
    }
    return 1;
}
int seed(char *p)
{
    int i;
    for (i=0 ; p[i] ; i++)
    {
        if (p[i]=='*') return i;
    }
    return -1;
}
int main()
{
    int test, maze_size, i, sx, sy;

    scanf("%d",&test);
    getchar();
    while (test--)
    {
        for (i=0 ;  ; i++)
        {
            gets(maze[i]);

            if (end(maze[i]))
                break;
        }

        maze_size = i;

        for (i=0 ; i<maze_size ; i++)
        {
            if ((sy = seed(maze[i]))>=0)
            {
                sx = i;
                break;
            }
        }

        dfs(sx,sy,maze_size,80);

        for (i=0 ; i<=maze_size ; i++)
            puts(maze[i]);

    }
    return 0;
}