WA50?
查看原帖
WA50?
556362
Unnamed114514楼主2023/4/1 11:57
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,m,tot,cnt,S,T,dfn[maxn],low[maxn],scc[maxn];
bool flg[maxn];
bool vis[maxn];
vector<int> G1[maxn],G2[maxn];
stack<int> s;
void Tarjan(int u,int fa){
	low[u]=dfn[u]=++tot;
	s.push(u);
	int num=0;
	for(auto v:G1[u]){
		if(v==fa)
			continue;
		if(!dfn[v]){
			Tarjan(v,u);
			++num;
			low[u]=min(low[u],low[v]);
			if(dfn[u]<=low[v]){
				scc[v]=++cnt;
				while(s.top()!=v){
					scc[s.top()]=cnt;
					s.pop();
				}
				s.pop();
				if(fa)
					flg[u]=1;
			}
		} else if(v!=fa)
			low[u]=min(low[u],dfn[v]);
	}
	if(!fa&&num>=2)
		flg[u]=1;
	if(!fa&&!num){
		s.pop();
		scc[u]=++cnt;
	}
}
void dfs(int u,int x){
	if(u==scc[T]){
		if(x==-1)
			puts("No solution");
		else
			printf("%d ",x);
		exit(0);
	}
	if(vis[u])
		return;
	vis[u]=1;
	for(auto v:G2[u])
		if(v>n){
			if(x==-1)
				dfs(v,v-n);
			else
				dfs(v,x);
		} else
			dfs(v,x);
}
int main(){
	scanf("%d",&n);
	int u,v;
	while(~scanf("%d%d",&u,&v)&&u){
		G1[u].push_back(v);
		G1[v].push_back(u);
	}
	scanf("%d%d",&S,&T);
	for(int i=1;i<=n;++i)
		if(!dfn[i])
			Tarjan(i,0);
	for(int i=1;i<=n;++i)
		if(flg[i]){
			for(auto v:G1[i]){
				if(flg[v]){
					G2[i+n].push_back(v+n);
					G2[v+n].push_back(i+n);
				} else{
					G2[i+n].push_back(scc[v]);
					G2[scc[v]].push_back(i+n);
				}
			}
		}
	dfs(scc[S],-1);
	puts("No solution");
	return 0;
}
2023/4/1 11:57
加载中...