圖論總結（2）無向圖的割頂和橋

概念：對于無向圖G，如果删除某個節點u後，連通分量的數目增加，則稱u為圖的關節點或割頂。

定理：在無向連通圖G的dfs樹中，非根節點u是G的割頂當且僅當u存在一個子節點v，使得v及其所有後代都沒有反向邊連回u的祖先(u不算)。

證明略；

友善起見，設low【u】為u及其後代所能連回的最早的祖先的pre（編号值）值，則定理中的條件就能夠簡寫為low（v）>=pre(u)；

如果後代隻能連回自己（即low（v）>pre（u）），隻需删除（u，v）就可以讓圖G非連通了，滿足這個條件的稱為橋。

int dfs(int u,int fa){
	int lowu=pre[u]=++dfs_clock;
	int child=0;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(!pre[v]){
			child++;
			int lowv=dfs(v);
			lowu=min(lowv,lowu);
			if(lowv>=pre[u]){//¸îµã 
				is_cut[u]=true;
			}
			if(lowv>pre[u]){//ÇÅ 
				is_bridge[u]=true;
			}
		}
		else if(pre[v]<pre[u]&&v!=fa){
			lowu=min(lowu,pre[v]);
		}
	}
	if(fa<0&&child==1)is_cut[u]=0;
	low[u]=lowu;
	return lowu;
}