24分求助!!!
查看原帖
24分求助!!!
151696
Konjacer楼主2021/5/28 20:55
#include<iostream>
#include<algorithm>
using namespace std;
struct edge{
	int next;
	int to;
	int w;
}dat[100005];
int cnt=1;
int head[100005];
void add(int u,int v,int w)
{
	dat[cnt].w=w;
	dat[cnt].to=v;
	dat[cnt].next=head[u];
	head[u]=cnt++;
}
const int po = 2e4+5;
int timee=1;
int dfn[po],low[po],fa[po];
int n,m,a,b;
int num=0;
int gd[po];
int gd_i=0;
void dfs(int x)
{
	dfn[x]=low[x]=timee++;
	int child=0;
	for(int i=head[x];i;i=dat[i].next)
	{
		int y=dat[i].to;
		//cout<<y<<endl;
		if(!dfn[y])
		{
			child++;
			fa[y]=x;
			dfs(y);
			if(fa[x]==-1&&child>=2)
			{
				//cout<<x<<"--------1"<<endl;
				num++;
				gd[++gd_i]=x;
				//cout<<x<<"is a gd!"<<endl;
			}
			if(fa[x]!=-1&&low[y]>=dfn[x])
			{
				//cout<<x<<"---------2"<<endl;
				//cout<<x<<" "<<y<<" "<<fa[x]<<" "<<low[y]<<" "<<dfn[x]<<endl;
				num++;
				gd[++gd_i]=x;
				//cout<<x<<"is a gd!"<<endl;
			}
		}
		else if(fa[x]!=y)
		{
			low[x]=min(low[x],dfn[y]);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		cin>>a>>b;
		add(a,b,1);
		add(b,a,1);
	}
	for(int i=1;i<=n;++i)
		fa[i]=-1;
	for(int i=1;i<=n;++i)
	{
		if(!dfn[i])
			dfs(i);
	}
	cout<<num<<endl;
	sort(gd+1,gd+1+gd_i);
	for(int i=1;i<=gd_i;++i)
	{
		cout<<gd[i]<<" ";
	}
	cout<<endl;
	return 0;
}
2021/5/28 20:55
加载中...