題目背景
割點
題目描述
給出一個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;
}