【洛谷 3388】割点

题目背景

割点

题目描述

给出一个nnn个点，mmm条边的无向图，求图的割点。

输入输出格式

输入格式：

第一行输入n,mn,mn,m

下面mmm行每行输入x,yx,yx,y表示xxx到yyy有一条边

输出格式：

第一行输出割点个数

第二行按照节点编号从小到大输出节点，用空格隔开

输入输出样例

输入样例#1： 复制 6 7 1 2 1 3 1 4 2 5 3 5 4 5 5 6 输出样例#1： 复制 1 5

说明

对于全部数据，n≤20000n \le 20000n≤20000，m≤100000m \le 100000m≤100000

点的编号均大于000小于等于nnn。

tarjan图不一定联通。

 

题解：模板割点题哈哈哈哈爽~

#include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int N=200004; int cnt,head[N],low[N],dfn[N],cut[N]; struct node{ int next; int m; }e[N]; int n,m,idx; void add (int x,int y){ cnt++; e[cnt].next=y; e[cnt].m=head[x]; head[x]=cnt; } void tarjan(int u,int fa){ dfn[u]=low[u]=++idx; int num=0; for(int i=head[u];i;i=e[i].m){ int v=e[i].next; if(!dfn[v]){ tarjan(v,fa); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u] && u!=fa) cut[u]=1; if(u==fa) num++; } low[u]=min(low[u],dfn[v]); } if(num>=2 && u==fa) cut[u]=1; } int main(){ freopen("3388.in","r",stdin); freopen("3388.out","w",stdout); scanf("%d %d",&n,&m); int a,b,ans=0; for(int i=1;i<=m;i++){ scanf("%d %d",&a,&b); add(a,b); add(b,a); } for(int i=1;i<=n;i++) if(dfn[i]==0) tarjan(i,i); for(int i=1;i<=n;i++) if(cut[i]!=0) ans++; cout<<ans<<endl; for(int i=1;i<=n;i++) if(cut[i]!=0) printf("%d ",i); return 0; }

 

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11152560.html