» » Articulation Point

Articulation Point

   4:48 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];

void dfs(int par, int u){
	int sz,i,v,child = 0;
	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]){
			child++;
			dfs(u,v);
			low[u] = _min(low[u],low[v]);
			if(low[v] >= d[u] && par!=-1)artp[u] = 1;
		}
		else low[u] = _min(low[u],d[v]);
	}
	if(par == -1 && child > 1 && !artp[u])artp[u] = 1;
}