回归选手求救
查看原帖
回归选手求救
184271
l55584楼主2022/1/24 21:30
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;int a,b;
vector<int> d[N];
int DFS[N],book[N],low[N],sz[N],fa[N];
int ans=0x3f3f3f3f;
vector<int> g;int cnt=0;
void dfs(int t)
{
	book[t]=1;
	DFS[t]=++cnt,low[t]=cnt;sz[t]=1;
	for(int i=0;i<d[t].size();i++)
	{
		if(fa[t]==d[t][i]) continue;
		if(book[d[t][i]]==0)
		{
			fa[d[t][i]]=t;
			dfs(d[t][i]);
			low[t]=min(low[t],low[d[t][i]]);
		}
		else low[t]=min(low[t],DFS[d[t][i]]);
		if(DFS[t]<=low[d[t][i]])
		{
			g.push_back(t);
		}
		sz[t]+=sz[d[t][i]];
	}
}
int main()
{
	cin>>n;
	int u,v;
	while(1)
	{
		cin>>u>>v;if(u==0) break;
		d[u].push_back(v);
		d[v].push_back(u);
	}
	cin>>a>>b;
	dfs(a);
	for(int i=0;i<g.size();i++)
	{
//		cout<<g[i]<<" ";
		if(DFS[g[i]]<DFS[b]&&DFS[b]<=DFS[g[i]]+sz[g[i]]-1)
		ans=min(ans,g[i]);
	}
//	cout<<endl;
//	for(int i=1;i<=n;i++) cout<<low[i]<<" "<<DFS[i]<<endl;
	if(ans==0x3f3f3f3f||ans==a) cout<<"No solution";
	else
	cout<<ans;
	return 0;
}

2022/1/24 21:30
加载中...