标签：tarjan read 图割点 int 无向 low dfn
//无向图割点模板
#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,
read,
图割点,
int,
无向,
low,
dfn
From： https://www.cnblogs.com/Charlieljk/p/17876048.html