【模板】(割点)(洛谷P3388)求割点!

xiaoxiao2021-03-01  3

题目:在哪呢?(<一戳他试试)

 

若是不想看题:求割点!(简洁明了,不愧是语文老师的文笔

 

割点:在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合。

 

如何求割点呢?鉴于此问题的简单,就由小华来解答一下!

小华(揉揉眼睛):呃……这道题目嘛!太简单了,我表示不屑于做!

 

小明:老师,他刚刚在睡觉,没听讲,连你问什么都不知道。

 

小华:你……我不和你玩了!!!!!!!

老师:那小明回答一下。

 

小明:啊!我也不会!换小猫来吧,她最厉害了。

 

小猫(极不情愿):遇事就叫我……下面是我的代码,不解释了。

 

#include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=10005; vector<int >p[N]; int fl[N],dfn[N],low[N]; int num,tot; void tarjan(int x,int root){ dfn[x]=low[x]=++num; for(int i=0;i<p[x].size();++i){ int v=p[x][i]; if(!dfn[v]){ tarjan(v,root); low[x]=min(low[x],low[v]); if(dfn[x]<=low[v]&&x!=root)fl[x]=1; if(x==root)tot++; } low[x]=min(low[x],dfn[v]); } if(x==root&&tot>=2)fl[root]=1; } int main(){ int n,m,x,y; cin>>n>>m; for(int i=1;i<=m;++i){ cin>>x>>y; p[x].push_back(y); p[y].push_back(x); } for(int i=1;i<=n;++i) if(!dfn[i])tarjan(i,i); int ans=0; for(int i=1;i<=n;++i) if(fl[i])ans++; printf("%d\n",ans); for(int i=1;i<=n;++i) if(fl[i]) printf("%d ",i); return 0; }

老师:小猫果然厉害,但是美中有个不足之处。

 

小猫:老师,我看到错误了。就是那个tot放错位置了。应该是:

#include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=10005; vector<int >p[N]; int fl[N],dfn[N],low[N]; int num; void tarjan(int x,int root){ int tot=0;//因为每次都要置零…… dfn[x]=low[x]=++num; for(int i=0;i<p[x].size();++i){ int v=p[x][i]; if(!dfn[v]){ tarjan(v,root); low[x]=min(low[x],low[v]); if(dfn[x]<=low[v]&&x!=root)fl[x]=1; if(x==root)tot++; } low[x]=min(low[x],dfn[v]); } if(x==root&&tot>=2)fl[root]=1; } int main(){ int n,m,x,y; cin>>n>>m; for(int i=1;i<=m;++i){ cin>>x>>y; p[x].push_back(y); p[y].push_back(x); } for(int i=1;i<=n;++i) if(!dfn[i])tarjan(i,i); int ans=0; for(int i=1;i<=n;++i) if(fl[i])ans++; printf("%d\n",ans); for(int i=1;i<=n;++i) if(fl[i]) printf("%d ",i); return 0; }

 

老师:小猫解释一下,为什么放外面不行。

 

小猫:由于每次都要更新根的子树个数,所以每次都要把它置零,放外面也行,但还是要更新tot的值,所以直接放里面更好。

 

老师:就是这样,还有什么问题吗?(读者有问题可以评论)

转载请注明原文地址: https://www.6miu.com/read-3849929.html

最新回复(0)