前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【模板】割点 tarjan

【模板】割点 tarjan

作者头像
用户2965768
发布2019-04-18 16:20:56
3210
发布2019-04-18 16:20:56
举报
文章被收录于专栏:wymwym

【模板】割点

 割点模版题

 dfn表示深搜次序,low表示该点可以到达的最远距离.无向图存双向边

若为根,有两个及以上孩子算割点,不为根,点u存在连接的一个点v访问的最小值low[v]大于等于(等于就是最后还是走到这个点)dfn[u],则u为割点

代码语言:javascript
复制
//tarjan割点
#include <bits/stdc++.h>
using namespace std;
const int M = 250000;
struct E{int v,nxt;};
E edge[M];
int n,m,head[M],dfn[M],low[M],cnt,bo[M];
int ans;
void tarjan(int u,int fa){
	dfn[u] = low[u] = ++cnt;
	int child = 0; 
	for(int v,i=head[u];i;i=edge[i].nxt){
		v = edge[i].v;
		if(!dfn[v]){
			tarjan(v,fa);
			low[u] = min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u!=fa){
				bo[u] = 1;
			}
			if(u==fa)
			child++;
		}else low[u] = min(low[u],dfn[v]);	
	} 
	if(child>=2)bo[fa]=1;
	
}
int main()
{
	scanf("%d %d",&n,&m);
	int ccnt = 0;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		ccnt++; edge[ccnt].v = v; edge[ccnt].nxt = head[u]; head[u]=ccnt;
		ccnt++; edge[ccnt].v = u; edge[ccnt].nxt = head[v]; head[v]=ccnt;	
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i,i);
	for(int i=1;i<=n;i++)if(bo[i])ans++; 
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)
	if(bo[i])printf("%d ",i);
	return 0;
 } 
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019年04月11日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档