Finding all bridges in a graph

find-all-bridges.cpp

vector<int> g[maxn];

int id = 1;
int pre[maxn];// pre[v] is the label for the vertex v
int l[maxn];// l[v] is the lowest label what we can reach from the vertex v

void dfs(int v, int parent){
	pre[v] = id++;
	l[v] = pre[v];// in the beginning this is the lowest label what we reach from here

	for(int i = 0; i < g[v].size(); ++i){
		int w = g[v][i];
		if( pre[w] == 0 ){
			dfs(w,v);
			
			// the lowest label for vertex v equals with the minimum label of it's children
			l[v] = min(l[v], l[w]); 
			
			if( l[w] == pre[w] ){//for w our statement is true, so we found a bridge
				cout << "Edge " << v << " " << w << " is bridge!" << endl;
			}
		} else if( w != parent ){ // we check all reachable vertices, doesn't matter, that we explored them before or not
			l[v] = min(l[v], l[w]);
		}
	}
}