本地运行测试用力没问题,但为啥再luogu上全re?
查看原帖
本地运行测试用力没问题,但为啥再luogu上全re?
598875
nikodo楼主2024/11/24 20:35
#include<bits/stdc++.h>
#define MAXN 100005 
using namespace std;
vector<int> v[MAXN],v1;
bool inst[MAXN],gd[MAXN];
int dfn[MAXN],low[MAXN];
int inde,root,total;
int tarjan(int x)
{
	++inde;
	dfn[x]=inde;
	low[x]=inde;
	inst[x]=1;
	int cnt=0;
	for(int i:v[x])
	{
		if(!dfn[i])
		{
			tarjan(i);
			cnt++;
			low[x]=min(low[x],low[i]);
			if(low[i]>=dfn[x]&&x!=root)
			{
				total++;
				gd[x]=1;
			}
		}
		else
		{
			low[x]=min(low[x],dfn[i]);
		}
	}
	if(x==root&&cnt>=2)
	{
		gd[x]=1;
	}
}
int main()
{
	int n,m,x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!inst[i])
		{
			root=i;
			tarjan(i);
		}
	}
	printf("%d\n",total);
	for(int i=1;i<=n;i++)
	if(gd[i])
		{printf("%d ",i);
	}
	return 0;
}
2024/11/24 20:35
加载中...