割点模板44分求助,已将输出改为空格
查看原帖
割点模板44分求助,已将输出改为空格
526895
WYZ20030051楼主2023/7/11 20:35
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<cstdlib>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
	int now=0,nev=1; 
	char c=getchar();
	while(c<'0' || c>'9') 
	{ 
		if(c=='-') 
			nev=-1; 
		c=getchar();
	}
	while(c>='0' && c<='9') 
	{ 
		now=(now<<1)+(now<<3)+(c&15); 
		c=getchar(); 
	}
	return now*nev;
}
const int MAXN=1e5+10;
const int MAXM=1e5+10;
int mod=998244353;
int n,m;
int head[MAXM],tt=0;
struct edge
{
	int to,nxt;
}e[MAXM<<1];
void add(int x,int y)
{
	e[++tt].nxt=head[x];
	head[x]=tt;
	e[tt].to=y;
}
int dfn[MAXN],low[MAXN],num=0;
bool cut[MAXN],ans=0;//cut[u]表示点u是不是割点,ans记录割点个数 
int root;
void Tarjan(int u)
{
	dfn[u]=low[u]=++num;
	int cnt=0;//记录子树个数 
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(!dfn[v])//若与u相连的点没有被遍历,说明点v所在的树为点u的子树 
		{
			Tarjan(v);
			cnt++;
			low[u]=min(low[u],low[v]);
			if((u==root && cnt>=2)||(u!=root && dfn[u]<=low[v]))
			{
				cut[u]=true;//点u为割点 
				ans++;
			}
			//判断一个点是割点的条件:
			//1.该点为树根且子树个数大于等于2。
			//2.该点不为树根且有dfn[u]<=low[v],即点u是点v与其它非子树点的必经之路,删去点u后点v无法到达自己的祖先 
		}
		else
			low[u]=min(low[u],dfn[v]);
	}
}
int main()
{
	memset(head,0,sizeof(head));
	memset(cut,false,sizeof(cut));
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int x,y;
		x=read(),y=read();
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			root=i;
			Tarjan(i);
		}
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)
	{
		if(cut[i])
			printf("%d ",i);
	}
	return 0;
}
2023/7/11 20:35
加载中...