首页 > 代码库 > 【模板】 Tarjan割点
【模板】 Tarjan割点
题目描述
给出一个n个点，m条边的无向图，求图的割点。
输入输出格式
输入格式：
第一行输入n,m
下面m行每行输入x,y表示x到y有一条边
输出格式：
第一行输出割点个数
第二行按照节点编号从小到大输出节点，用空格隔开
输入输出样例
输入样例#1：
6 71 21 31 42 53 54 55 6输出样例#1：
1 5说明
n,m均为100000
tarjan 图不一定联通！！！
1 #include<iostream> 2 #include<cstdio> 3 #define int long long 4 using namespace std; 5 const int MAXN=200010; 6 struct XY{int to,pre;}e[MAXN*2]; 7 int las[MAXN],dfn[MAXN],low[MAXN],res[MAXN]; 8 int tim=0,sz=1,ans=0,n,m,x,y; 9 10 void add(int a,int b){11 e[++sz].to=b;e[sz].pre=las[a];las[a]=sz;12 e[++sz].to=a;e[sz].pre=las[b];las[b]=sz;13 }14 15 void tarjan(int u,int fa){16 int son=0,v;17 dfn[u]=low[u]=++tim;18 for (int i=las[u];i;i=e[i].pre)19 if (!dfn[v=e[i].to]){20 son++;tarjan(v,u);21 low[u]=min(low[u],low[v]);22 if (dfn[u]<=low[v]&&!res[u]) ans++,res[u]=1;23 }else if (v!=fa) low[u]=min(low[u],dfn[v]);24 if (fa==-1&&son==1) res[u]=0,ans--;25 }26 27 main(){28 cin >>n>>m;29 for (int i=1;i<=m;++i) scanf("%lld%lld",&x,&y),add(x,y);30 for (int i=1;i<=n;++i) if (!dfn[i]) tarjan(i,-1);31 cout <<ans<<endl;32 for (int i=1;i<=n;++i) if (res[i]) printf("%lld ",i);33 return 0;34 }
【模板】 Tarjan割点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。