求助 tarjan算法RE ?
查看原帖
求助 tarjan算法RE ?
896179
Hurraciny楼主2023/12/1 21:59
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef struct{
	int to;
	int nxt;
}EDGE;
int n, q;
EDGE edge[100002];
int head[100002];
int cnt = 0;
inline void add_edge(int u, int v){
	edge[cnt].to = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt++;
	return;
}
typedef struct{
	int to;
	int idx;
	int nxt;
}QUERY;
QUERY query[100002];
int qhead[100002];
inline void add_query(int x, int y, int num){
	query[cnt].to = y;
	query[cnt].idx = num;
	query[cnt].nxt = qhead[x];
	qhead[x] = cnt++;
	return;
}
int fa[100002];
inline int find(int x){
	if(x == fa[x])
		return x;
	return fa[x] = find(fa[x]);
}
inline void join(int x, int y){
	x = find(x);
	y = find(y);
	fa[x] = y;
	return;
}
int dis[100002];
int ans[100002];
bool vis[100002];
inline void tarjan(int x){
	for(int i = head[x]; ~i; i = edge[i].nxt)
		if(!vis[edge[i].to]){
			dis[edge[i].to] = dis[x] + 1;
			vis[edge[i].to] = true;
			tarjan(edge[i].to);
			join(edge[i].to, x);
		}
	for(int i = qhead[x]; ~i; i = query[i].nxt)
		if(vis[query[i].to])
			ans[query[i].idx] = dis[x] + dis[query[i].to] - 2*dis[find(query[i].to)];
	return;
}
int main(){
	memset(head, -1, sizeof(head));
	memset(qhead, -1, sizeof(qhead));
	scanf("%d", &n);
	for(int i = 1; i < n; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		add_edge(u, v);
		add_edge(v, u);
	}
	cnt = 0;
	scanf("%d", &q);
	for(int i = 1; i <= q; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		add_query(x, y, i);
		add_query(y, x, i);
	}
	for(int i = 1; i <= n; i++)
		fa[i] = i;
	vis[1] = true;
	tarjan(1);
	for(int i = 1; i <= q; i++)
		printf("%d\n", ans[i]+1);
	return 0;
}	

求助 第四个点re?

2023/12/1 21:59
加载中...