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