求调wa subtask#1
查看原帖
求调wa subtask#1
592897
GrainRain25楼主2024/7/2 10:06
#include<bits/stdc++.h>
using namespace std;
template <typename T> void read(T &x){
	int f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
const int maxn=1e6+5,maxm=1e5+5;
int a,b,n,tot,t;
int dfn[maxn],low[maxn],cut[maxn],head[maxn],ver[maxm*2],Next[maxm*2];

void add(int x,int y){
	ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
}

void tarjan(int x,int fa){
	dfn[x]=low[x]=++t;
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(!dfn[y]){
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]&&x!=a&&dfn[b]>=dfn[y])
				cut[x]=1;
		}
		else if(y!=fa)low[x]=min(low[x],dfn[y]);
	}
}

int main(){
	read(n);
	int x,y;
	do{
		read(x);read(y);
		add(x,y);add(y,x);
	}while(x||y);
	read(a);read(b);
	tarjan(a,0);
	for(int i=1;i<=n;i++){
		if(cut[i]){
			printf("%d\n",i);
			return 0;
		} 
	}
	printf("No solution\n");
	return 0;
} 
2024/7/2 10:06
加载中...