luogu3388 割点（模板）

luogu3388 割点（模板）

​​ 题目背景

割点

题目描述

给出一个n个点，m条边的无向图，求图的割点。

输入输出格式

输入格式：

第一行输入n,m

下面m行每行输入x,y表示x到y有一条边

输出格式：

第一行输出割点个数

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

输入输出样例

输入样例#1：

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

1 5 说明

n,m均为100000

tarjan 图不一定联通！！！

tarjan求割点

输出一行 我多行，40分刷了很久

#include#include#include#includeusing namespace std;#define N 110000inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}set q;struct node{ int y,next;}data[N<<1];int h[N],dfn[N],low[N],num,fa[N],n,m;bool ap[N];void tarjan(int u){ int child=0;dfn[u]=low[u]=++num; for (int i=h[u];i;i=data[i].next){ int v=data[i].y; if (fa[u]==v) continue; if (!dfn[v]) { child++;fa[v]=u;tarjan(v);low[u]=min(low[u],low[v]); if (fa[u]==-1&&child>=2) q.insert(u); if (fa[u]!=-1&&low[v]>=dfn[u]) q.insert(u); }else low[u]=min(low[u],dfn[v]); }}int main(){ freopen("3388.in","r",stdin); n=read();m=read();memset(fa,-1,sizeof(fa)); for (int i=1;i<=m;++i){ int x=read(),y=read(); data[++num].y=y;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].next=h[y];h[y]=num; }num=0; for (int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); printf("%d\n",q.size()); set::iterator i; for (i=q.begin();i!=q.end();++i) printf("%d ",*i); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。