tarjan无向图割点板子-526互联

//无向图割点模板
#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define N 20001
using namespace std;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool f=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(f?x:~x+1);
}
int n,m,a,b,tot,root,ans,dfn[N],low[N];
bool cut[N];
vector<int> e[N];
void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	int child=0;
	for(int y:e[x])
		if(!dfn[y])
		{
			tarjan(y),
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x])
			{
				child++;
				if(x!=root||child>1) cut[x]=1;
			}
		} 
		else low[x]=min(low[x],dfn[y]);
}
signed main()
{
	#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
	read(n),read(m);
	while(m--) 
		read(a),read(b),
		e[a].push_back(b),
		e[b].push_back(a);
	for(root=1;root<=n;root++)
		if(!dfn[root]) tarjan(root);
	for(int i=1;i<=n;i++) if(cut[i]) ans++;
	cout<<ans<<endl;
	for(int i=1;i<=n;i++) if(cut[i]) cout<<i<<' ';
}

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

板子

tarjan