就是记录两个数组:dfn[]
和low[]
其中dfn[]
表示访问的顺序,low[u]
用来存储 \(u\) 不经过其父亲能到达的最小时间戳。。。
搬一下 wiki 的图。。。
我们发现 \(low[v]\ge dfn[u]\) 可以表示不能回到祖先,则 \(u\) 点位割点。。。
直接上代码P3388------>
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int r;
int n,m,book[N];
int dfn[N],low[N];
vector <int> k[N];
int id=0,cnt;
void dfs(int x,int fa)
{id++;dfn[x]=id;low[x]=id;int son=0;for(int i=0;i<k[x].size();i++){int y=k[x][i];if(!dfn[y]){son++;dfs(y,x);low[x]=min(low[x],low[y]);if(low[y]>=dfn[x]&&x!=r){cnt+=!book[x];book[x]=1;}}else{if(1){low[x]=min(low[x],dfn[y]);}}}if(x==r&&son>1){cnt+=!book[x];book[x]=1;}return;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);k[x].push_back(y);k[y].push_back(x);}for(int i=1;i<=n;i++){if(!dfn[i]){r=i;dfs(i,0);}}cout<<cnt<<"\n";for(int i=1;i<=n;i++){if(book[i]==1)cout<<i<<" ";}return 0;
}