首页 > 代码库 > 割点算法模板(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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。