首页 > 代码库 > 洛谷 P3388 【模板】割点
洛谷 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 <algorithm>#include <ctype.h>#include <cstring>#include <cstdio>#define N 100005using namespace std;void read(int &x){ x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) { x=x*10+ch-‘0‘; ch=getchar(); }}bool vis[N],cutpoint[N],cutedge[N];int ans[N],l,low[N],dfn[N],tim,n,m,cnt=-1,head[N];struct node{ int next,to;}edge[N<<1];void add(int u,int v){ ++cnt; edge[cnt].next=head[u]; edge[cnt].to=v; head[u]=cnt;}int min(int a,int b){return a>b?b:a;} void tarjan(int x,int pre){ low[x]=dfn[x]=++tim; vis[x]=1; int sum=0; bool flag=false; for(int i=head[x];i!=-1;i=edge[i].next) { if((i^1)!=pre) if(!vis[edge[i].to]) { sum++; tarjan(edge[i].to,i); if(low[edge[i].to]>=dfn[x]) flag=true; low[x]=min(low[x],low[edge[i].to]); } else low[x]=min(low[x],dfn[edge[i].to]); } if(pre==-1) { if(sum>1) cutpoint[x]=true; } else { if(flag) cutpoint[x]=true; } }int main(){ memset(head,-1,sizeof(head)); read(n);read(m); for(int x,y;m--;) { read(x);read(y); add(x,y); add(y,x); } for(int i=1;i<=n;i++) if(!vis[i]) tarjan(i,-1); for(int i=1;i<=n;i++) if(cutpoint[i]) l++,ans[l]=i; printf("%d\n",l); for(int i=1;i<=l;i++) printf("%d ",ans[i]); return 0;}
洛谷 P3388 【模板】割点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。