【洛谷P3388】【模板】割点

Dear 丶 2021-09-29 23:10 361阅读 0赞

都快忘了割点怎么搞了

对所有点分两类

1.根节点 2.非根节点

显然根节点是很好做的 只需要数一下有没有两个子树以上

对于非根节点 利用tarjan算法

回忆到dfn的定义：时间戳，即在dfs中第几个被访问到 low：经过最多一条后向边/栈中横叉边能到达的最小的节点时间戳

对于当前节点now来说，把整个图分成了两个子树。假如low\[vis\]>=dfn\[now\]，(注意不要把时间戳和编号序搞混) 也就是说vis节点最多只能追溯到now这棵子树以内，而不能回到另一颗子树去。就因为这个特殊的vis，now就成了割点。

然后注意细节吧 比如输出 以及统计答案要单独扫一遍 因为会有重复的

#include<bits/stdc++.h> #define N 20005 #define M 100005 using namespace std; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } struct Edge { int to,next,val; }edge[2*M]; int n,m,tot,first[N]; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } int dfn[N],low[N],sign,cnt; bool cut[N]; inline void dfs(int now,int fa) { int child=0; dfn[now]=low[now]=++sign; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; if(!dfn[vis]) { ++child; dfs(vis,now); low[now]=min(low[vis],low[now]); if(low[vis]>=dfn[now]&&fa!=0) cut[now]=true; //非根节点 } else low[now]=min(low[now],dfn[vis]); } if(fa==0&&child>=2) cut[now]=true; //根节点 } int main() { read(n); read(m); for(int i=1,u,v;i<=m;i++) read(u),read(v),addedge(u,v),addedge(v,u); for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,0); for(int i=1;i<=n;i++) if(cut[i]) ++cnt; //注意要在这里扫一遍 而不是在dfs里记录 因为会重复 cout<<cnt<<endl; for(int i=1;i<=n;i++) if(cut[i]) cout<<i<<" "; return 0; }

转载于:https://www.cnblogs.com/Patrickpwq/articles/9870608.html