#10 WA 找不到错,求助
查看原帖
#10 WA 找不到错,求助
577581
00000110hh楼主2022/5/24 18:31
#include<bits/stdc++.h>
using namespace std;
int n;
int x,y;
int a,b;
struct node{
	int v;
	int nex;
}e[2000005];
int head[500005];
int cnt;
void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].nex=head[u];
	head[u]=cnt;
	e[++cnt].v=u;
	e[cnt].nex=head[v];
	head[v]=cnt;
	return;
}
int dfn[500005],low[500005];
bool key[500005];
int num;
int ans=1e9;
void tarjan(int u){
	dfn[u]=++num;
	low[u]=dfn[u];
	for(int i=head[u];i;i=e[i].nex){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v);
            low[u]=min(low[v],low[u]);
			if(low[v]>=dfn[u]&&dfn[u]<dfn[b]&&u!=a){//只有搜过b dfn[b]才有值,只有同一颗子树才小于 
					ans=min(u,ans);
			}
		}
		else {
			low[u]=min(low[u],dfn[v]);//上浮 
		}
	}
	return;
}
int main(){
	cin>>n;
	while(1){
		cin>>x>>y;
		if(x==0&&y==0) break;
		add(x,y);
		
	}
	cin>>a>>b;
	tarjan(a);
	if(ans==1e9)cout<<"No solution";
	else cout<<ans;
	return 0;
}
2022/5/24 18:31
加载中...