之前还有个思路错了一样的点,怀疑是什么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;
}