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