求割点

割点的性质,注意访问过的点的取最小值的方式。

#include <bits/stdc++.h>
using namespace std;

using ll=long long;

ll n,m,ans,dfn[(int)2e4+9],low[(int)2e4+9],dfncnt;
bitset<int(2e4+9)>vis;
vi g[(int)2e4+9];

void tarjan(int u,int anc){
	dfn[u]=low[u]=++dfncnt;
	//cerr<<u<<"::"<<dfn[u]<<" "<<low[u]<<"\n";
	int child=0;
	for(auto v:g[u]){
		if(!dfn[v]){
			tarjan(v,anc),low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u!=anc) vis[u]=true;//如果儿子的low值大于等于dfn,则代表其为儿子与其他非子树点相连的唯一途径
			if(u==anc) child++;
		}
		else low[u]=min(low[u],dfn[v]);
		//cerr<<v<<"--->"<<u<<"::"<<dfn[u]<<" "<<low[u]<<"\n";
	}
	if(child>=2&&u==anc) vis[u]=true;//对根的处理
} 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1,x,y;i<=m;++i){
    	cin>>x>>y;
    	g[x].push_back(y),g[y].push_back(x);
    }
    for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i,i);
    cout<<vis.count()<<"\n";
    for(int i=1;i<=n;++i)if(vis[i])cout<<i<<" ";
    return 0;
}

上一篇
下一篇