求助!!!waon4 6 7 10
查看原帖
求助!!!waon4 6 7 10
1065103
Atri_Lobato楼主2024/9/29 21:46

之前还有个思路错了一样的点,怀疑是什么nc错误,比方说Tarjan错了qaq

#include<iostream>
using namespace std;
int n;
int pic[200005];
struct Edge
{
	int nxt,to;
}edge[1000005];
int a,b;
int tot=0;
void add(int from,int to)
{
	tot++;
	edge[tot].to=to;
	edge[tot].nxt=pic[from];
	pic[from]=tot;
}
int order=0;
int dfn[200005];
int low[200005];
bool cut[200005];
int in[200005];
void Tarjan(int now,int fa)
{
	order++;
	dfn[now]=order;
	low[now]=order;
	int cnt=0;
	for(int i=pic[now];i;i=edge[i].nxt)
	{
		int np=edge[i].to;
		if(np==fa)
		continue;
		if(dfn[np]==0)
		{
			Tarjan(np,now);
			low[now]=min(low[now],low[np]);
			if(low[np]>=dfn[now])
			{
				cut[now]=1;
			}
		}
		else
		{
			low[now]=min(low[now],dfn[np]);
		}
	}
	in[now]=order;
}
int main()
{
	scanf("%d",&n);
	a=1;
	while(!(a==0&&b==0))
	{
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	scanf("%d%d",&a,&b);
	Tarjan(a,0);
	if(dfn[b]==0)
	{
		printf("No solution");
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(i==a)
		continue;
		if(cut[i]==1&&dfn[a]<dfn[i]&&dfn[i]<dfn[b]&&dfn[b]<=in[i])
		{
			cout<<i;
			return 0;
		}
	}
	printf("No solution");
	return 0;
}
2024/9/29 21:46
加载中...