92分求助
查看原帖
92分求助
544062
pigonered楼主2021/10/11 13:13
#include<bits/stdc++.h>
using namespace std;

#define num ch-'0'
void get(int &res)
{
    char ch;bool flag=0;
    while(!isdigit(ch=getchar()))
        (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getchar());res=res*10+num);
    (flag)&&(res=-res);
}

const int N=1e8+5;
int n,m,low[N],dfn[N],sum,cnt,son;
bool cut[N];
int first[N],nex[N],to[N],tot;

void add(int x,int y)
{
	nex[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
}

void dfs(int x,int fa)
{
	dfn[x]=low[x]=++cnt;
	son=0;//
	for(int i=first[x];i;i=nex[i])
	{
		int y=to[i];
		if(dfn[y]==0)
		{
			dfs(y,fa);//
			low[x]=min(low[y],low[x]);
			if(low[y]>=dfn[x] && x!=fa) cut[x]=1;
			if(x==fa) son++;
		}
		else
			low[x]=min(low[x],dfn[y]);//
	}
	if(son>=2 && x==fa)	cut[x]=1;
}

int main()
{
	get(n);get(m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		get(x);get(y);
		add(x,y);//
		add(y,x);//
	}
	
	for(int i=1;i<=n;i++)
	{
		if(dfn[i]==0) dfs(i,i);//
	}
	
	for(int i=1;i<=n;i++)
	{
		if(cut[i]) sum++;
	}
	cout<<sum<<endl;
	for(int i=1;i<=n;i++)
	{
		if(cut[i]) cout<<i<<" ";
	}
	return 0;
}

求大佬求助

2021/10/11 13:13
加载中...