NO IMAGE

題目背景

割點

題目描述

給出一個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 圖不一定聯通!!!
.
.
.
.
.

目錄
程式:
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n,m;
int head[100005],bel[100005],dfn[200005],low[200005];
int stack[100005],to[200005],nex[200005],fa[200005],tot;
int cnt=1;
bool cut[200005];
void add(int x,int y)
{
tot  ;
nex[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void tarjan(int p)
{
int rd=0;
dfn[p]=low[p]=  cnt;
for (int i=head[p];i;i=nex[i])
{
int v=to[i];
if (!dfn[v])
{
fa[v]=fa[p];
tarjan(v);
low[p]=min(low[p],low[v]);
if (low[v]>=dfn[p]&&p!=fa[p]) cut[p]=true;
if (p==fa[p]) rd  ;
}
low[p]=min(low[p],dfn[v]);
}
if (p==fa[p]&&rd>=2) cut[fa[p]]=true;
}
int main()
{
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);
}
memset(dfn,0,sizeof(dfn));
for(int i=1;i<=n;i  ) 
fa[i]=i;
for(int i=1;i<=n;i  )
if (!dfn[i]) tarjan(i);
int ans=0;
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;
}