首页 > 代码库 > 割点算法模板(Cut-vertex)

割点算法模板(Cut-vertex)

下面是求割點的模板,還有cut_vertex_num[]數組(array)記錄了哪些是割點

Int cut_vertex_num[];void dfs(int cur,int pa){  int child=0,flag=0,i;  low[cur]=dfn[cur]=++depth;  for(i=0;i<adj[cur].size();i++)    {    int next=adj[cur][i];    if(!dfn[next])	//若未访问过      {       child++;       dfs(next,cur);       low[cur]=min(low[next],low[cur]);//沒有back edge返回自己的祖先,相等則為最多返回到自己,設定flag標記       if(low[next]>=dfn[cur]) flag=1;      }      else if(next!=pa) //若已访问过        low[cur]=min(low[cur],dfn[next]);}//若有兩個以上子節點或該節點非root,且割點前提條件成立,則該點為割點   if((child>=2 || pa>=0) && flag)      cut_vertex_num[++ans]=cur;   return;}