求助,tarjan,只有70分啊
查看原帖
求助,tarjan,只有70分啊
832745
yojawe楼主2023/4/30 20:55

实在是看不出来哪里错了,求助大佬们。。

#include <bits/stdc++.h>
using namespace std;
const long N=6e5+10;
long vis[N]={0},Next[N]={0},head[N]={0},edge[N]={0},ver[N]={0};
long fa[N]={0},d[N]={0},ans[N]={0};

vector<pair<long,long> > query[N];
long n,m,a,b,c,tot=0,s;
void add(long x,long y,long data){
	ver[++tot]=y,edge[tot]=data,Next[tot]=head[x],head[x]=tot;
}
void add_query(long x,long y,long dex){
	query[x].push_back({y,dex});
	query[y].push_back({x,dex});
}
long find(long x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void tarjan(long u){
	vis[u]=1;
	for(long i=head[u];i;i=Next[i]){
		long y=ver[i];
		if(!vis[y]){
			d[y]=d[u]+1;
			tarjan(y);
			fa[y]=u;
		}
	}
	for(auto it:query[u]){
		long y=it.first,dex=it.second;
		if(vis[y]==2){
			long lca=find(y);
			ans[dex]=lca;
		}
	}
	vis[u]=2;
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(long i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		add(a,b,1);
		add(b,a,1);
	} 
	for(long i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		if(a==b) ans[i]=a;
		else add_query(a,b,i);
	}
	for(long i=1;i<=n;i++) fa[i]=i;
	tarjan(s);
	for(long i=1;i<=m;i++){
		if(i!=m)
		printf("%ld\n",ans[i]);
		else printf("%ld",ans[i]);
	}
	return 0;
} 
2023/4/30 20:55
加载中...