首页 > 代码库 > 洛谷P3388 【模板】割点
洛谷P3388 【模板】割点
给出一个n个点，m条边的无向图，求图的割点。
u是cut vertex的两个条件：
1.存在v使v及其所有后代没有反向边连回u的祖先
2.u是根且有两个以上子节点
dfs一遍
low[u]是u及其后代所能连回的最早祖先
没有dfn[v]就dfs(v)，然后用low[v]更新low[u]（v是u的后代）
否则v不是fa就用dfn[v]更新low[u]（u可以连回v）【不能用low[v]，因为low[v]包含v的后代能连回】
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=1e5+5,M=1e5+5,INF=1e9+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x;}int n=0,m,u,v;struct edge{ int v,ne;}e[M<<1];int h[N],cnt=0;inline void ins(int u,int v){ cnt++; e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;}int dfn[N],low[N],dfc=0,iscut[N];void dfs(int u,int fa){ dfn[u]=low[u]=++dfc; int child=0; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!dfn[v]){ child++; dfs(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]) iscut[u]=1; }else if(dfn[v]<dfn[u]&&v!=fa) low[u]=min(low[u],dfn[v]); } if(fa==0&&child==1) iscut[u]=0;}int main(){ n=read();m=read(); for(int i=1;i<=m;i++){u=read();v=read();ins(u,v);} for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,0); int ans=0; for(int i=1;i<=n;i++) if(iscut[i]) ans++; printf("%d\n",ans); for(int i=1;i<=n;i++) if(iscut[i]) printf("%d ",i);}
洛谷P3388 【模板】割点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。