一个小问题
查看原帖
一个小问题
658786
STUDENT00楼主2022/11/12 22:44

额,RT,我加了那句话WA100,删了那句话AC100:

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,ans=1e9,dfn[200010],low[200010],cnt;
bool ok[200010];
vector<int> w[200010];
void tarjan(int now,int fir){
	dfn[now]=low[now]=++cnt;
	int s=0;
	for(int i=0;i<w[now].size();i++){
		int t=w[now][i];
		if(!dfn[t]){
			s++;
			tarjan(t,fir);
			low[now]=min(low[now],low[t]);
			if(now!=fir&&low[t]>=dfn[now]&&dfn[b]>=dfn[t]) ok[now]=1;
		}else low[now]=min(low[now],dfn[t]);
	}
	//if(now==fir&&s>=2) ok[now]=1;
}
int main(){
	scanf("%d",&n);
	int u,v;
	while(scanf("%d%d",&u,&v)&&(u||v)){
		m++;
		w[u].push_back(v);
		w[v].push_back(u);
	}
	scanf("%d%d",&a,&b);
	tarjan(a,a);
	for(int i=1;i<=n;i++){
		if(ok[i]){
			printf("%d",i);
			return 0;
		}
	}
	printf("No solution");
	return 0;
}
2022/11/12 22:44
加载中...