» » Bridge Network

Bridge Network

   4:50 PM       

 
#define mx 110
#define _min(i,j) ((i)>(j)?(j):(i))

int d[mx],low[mx],t;
bool color[mx],artp[mx];
vector < int > M[mx];
vector < pii > bridge;
void dfs(int par, int u){
	int sz,i,v;
	low[u] = d[u] = ++t;
	color[u] = 1;
	sz = M[u].size();
	for(i=0;i<sz;i++){
		v = M[u][i];
		if(v==par)continue;
		if(!color[v]){
			dfs(u,v);
			low[u] = _min(low[u],low[v]);
			if(low[v] > d[u])
				bridge.push_back(pii(u,v));
		}
		else low[u] = _min(low[u],d[v]);
	}
}