图算法割点

2024-04-21 00:32

文章标签 算法割点

本文主要是介绍图算法割点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OJ链接: P3388 【模板】割点（割顶）

算法流程

初始化：now[cur]=low[cur]=当前索引
循环：对cur结点的所有邻接结点进行遍历
　　如果未访问：
　　　　孩子++
　　　　DFS
　　　　用子结点的low[to]更新自己
　　　　割点判断（分为是否根节点）
　　如果已访问：并且遍历的后继不是父节点：
　　　　用子结点的now[to]更新自己

#include <bits/stdc++.h>#define I scanf
#define OL puts
#define O printf
#define F(a,b,c) for(a=b;a<c;a++)
#define FF(a,b) for(a=0;a<b;a++)
#define FG(a,b) for(a=b-1;a>=0;a--)
#define LEN 100010
#define MAX 0x06FFFFFF
#define V vector<int>using namespace std;struct edge{int to,next;
}mp[LEN*2]; //边表 
int head[LEN*2];//顶点u出发的第一条边
int cnt=0;  //边表索引 
void add (int u,int v){mp[cnt].to=v;mp[cnt].next=head[u];   //指针向前head[u]=cnt++;          //边表索引增加 
}int N,M;
int now[LEN];
int low[LEN];
int flag[LEN];
int Index=0;
int root; 
vector<int> ans;void dfs(int cur,int father) {int child=0,i,j;Index++;now[cur]=Index;low[cur]=Index;for(i=head[cur];~i;i=mp[i].next){  //遍历cur的所有结点 int to=mp[i].to;if(now[to]==0) {    //没有访问过 child++;dfs(to,cur);//递归完了，现在是栈底low[cur] =min(low[cur],low[to]);//用子结点的最小时间戳更新自己的最小时间戳if(cur!=root && low[to]>=now[cur] ){    //子结点能回溯到的最小时间戳比父节点还大：父节点为割点 flag[cur] =1;}if(cur==root && child>=2){flag[cur] =1;       }}else if(to!=father) {low[cur]=min(low[cur],now[to]);//用子结点的最小时间戳更新自己的最小时间戳}}
}void init(){memset(head,-1,sizeof head);
}int main(){
//    freopen("P3388-割点.txt","r",stdin);
//    freopen("testdata.in","r",stdin);init();int i,a,b;I("%d%d",&N,&M);FF(i,M){I("%d%d",&a,&b);add(a,b);add(b,a);}for(i=1;i<=N;i++) if(now[i]==0) {root=i;dfs(i,0);}for(i=1;i<=N;i++) if(flag[i]) ans.push_back(i);int sz=ans.size(); O("%d\n",sz);FF(i,sz){O("%d",ans[i]);if(i!=sz-1) O(" ");}return 0;
}