蒟蒻求救!
查看原帖
蒟蒻求救!
339299
osfly楼主2021/8/1 21:08
#include<cstdio>
struct edge
{
	int v,nxt;
}e[200001];
int head[20001],tot=1;
int n,m;
int index,low[20001],dfn[20001];
bool flag[20001];
int root;
int cnt;
void add(int u,int v)
{
	e[tot].v=v;
	e[tot].nxt=head[u];
	head[u]=tot++;
}
int min(int a,int b)
{
	return a<b?a:b;
}
void dfs(int curr,int f)
{
	int child=0;
	low[curr]=dfn[curr]=++index;
	for(int i=head[curr],v;i!=-1;i=e[i].nxt)
	{
		v=e[i].v;
		if(!dfn[v])
		{
			child++;
			dfs(v,curr);
			low[curr]=min(low[curr],low[v]);
			if((curr!=root&&low[v]>=dfn[curr])||(curr==root&&child==2))
			{
				flag[curr]=true;
				cnt++;
			}
		}
		else if(v!=f) low[curr]=min(low[curr],dfn[v]);
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) head[i]=-1;
	for(int i=1,u,v;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++)
		if(dfn[n]==0)
		{
			root=i;
			dfs(i,i);
		}
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++)
		if(flag[i]) printf("%d\n",i);
	return 0;
 } 

#1 #4 #6 #7 #8 #10 #11 WA了

2021/8/1 21:08
加载中...