[ Articulation Vertex ] 割點

關節點(割點)是讓一張無向圖維持連通，不可或缺的點。只要從一張無向圖上移除了關節點（以及與之相連的邊），就會讓這張圖分離成更多部分，呈現不連通的狀態。
存在一種線性算法找出一張圖所有的割點，一個dfs就能解決了

以下提供模板:

	#include<vector>
	#include<algorithm>
	#define N 50005
	std::vector<int> s[N];
	int low[N],v[N]={0},Time=0,ans=0;
	void dfs(int x,int p){/*x當前點，p父親*/
	int i,r,is=0,add=0;
	low[x]=v[x]=++Time;
	for(i=0;i<(int)s[x].size();++i){
	if(!v[r=s[x][i]]){
	dfs(r,x),++add;
	low[x]=std::min(low[x],low[r]);
	if(v[x]<=low[r])is=1;
	}
	if(r!=p)low[x]=std::min(low[x],v[r]);
	}/*傳回有幾個割點*/
	if(is)++ans;
	if(x==p&&add<2)--ans;/*x是dfs樹的根要特判*/
	}

view raw Articulation Vertex.cpp hosted with ❤ by GitHub