首页 > 代码库 > luogu P3388 【模板】割点（割顶）
luogu P3388 【模板】割点（割顶）
题目背景
割点
题目描述
给出一个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 图不一定联通！！！
#include<cstdio>#include<algorithm>#define N (1000000+10)using namespace std;int a[N],nxt[N],head[N],dfn[N],low[N],cnt,k;bool cut[N],bst[N];void add(int x,int y){ a[++k]=y; nxt[k]=head[x]; head[x]=k;}void tarjan(int u,int mr){ int rc=0; dfn[u]=low[u]=++cnt; for (int p=head[u];p;p=nxt[p]) { int v=a[p]; if (!dfn[v]) { tarjan(v,mr); low[u]=min(low[u],low[v]); if (low[v]>=dfn[u]&&u!=mr) cut[u]=true; if (u==mr) rc++;//根节点的孩子 } low[u]=min(low[u],dfn[v]); } if (u==mr&&rc>=2) cut[mr]=true;}int main(){ int n,m,ans=0; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } for (int i=1;i<=n;i++) { if (!dfn[i]) tarjan(i,i);//防止遗漏 } for (int i=1;i<=n;i++) if (cut[i]) ans++; printf("%d\n",ans); for (int i=1;i<=n;i++) if (cut[i]) printf("%d ",i); return 0;}
luogu P3388 【模板】割点（割顶）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。