tarjan全T求调
查看原帖
tarjan全T求调
175533
Gianthard_陈昱衡楼主2023/9/25 16:44

不知道是什么问题,感觉其他人的tarjan跟我的也差不多啊(?

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int ans[500010],que[500010],headq[500010],head[500010],fa[500010],tote=0,totq=0;
bool vis[500010];
template <typename T> 
struct ch{
	int nxt;
	T v;
};
ch<int> e[500010];
ch< pair<int,int> > qt[500010];

int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}

int DFS(int now){
	for(int k=head[now];k;k=e[k].nxt){
		vis[now]=true;
		if(!vis[e[k].v]){
			DFS(e[k].v);
			fa[e[k].v]=now;
		}
		for(int k=headq[now];k;k=qt[k].nxt){
			if(vis[qt[k].v.first])ans[qt[k].v.second]=find(qt[k].v.first); 
		}
	}
}

void adde(int x,int y){
	e[++tote].v=y;
	e[tote].nxt=head[x];
	head[x]=tote;
}

void addq(int x,int y,int i){
	qt[++totq].v.first=y;
	qt[totq].v.second=i;
	qt[totq].nxt=headq[x];
	headq[x]=totq;
}

int main(){
	cin>>n>>m>>s;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n-1;i++){
		int x,y;cin>>x>>y;
		adde(x,y);adde(y,x);
	}
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		addq(x,y,i);addq(y,x,i)
	}
	DFS(s);
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}
2023/9/25 16:44
加载中...