代码

P3379 【模板】最近公共祖先(LCA):Tarjan算法离线实现

[success]原题:https://www.luogu.org/problem/show?pid=3379[/success]
题意,给你一棵树,求几对点的LCA...

我的做法:
由于Tarjan够简单的,所以我就用了Tarjan...
这个算法真的很简单!!但是超级好理解的!!
以前从来没写过LCA...这也是第一次吧

O(α(n) + M)

代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 600050
#define MAXM 600050
using namespace std;
int headt[MAXN], headq[MAXN];
int ans[MAXM];
int f[MAXN], vis[MAXN];
int n, m, s;
int tec = 0, qec = 0;

struct edge{
	int to, next;
}te[MAXN * 2];

struct edg2{
	int to, next, idx;
}qe[MAXN * 2];

int fin(int v){
//	cout << v << endl;
	if (f[v] != v) f[v] = fin(f[v]);
	return f[v];
}

void tarjan(int u){
//	cout << u << endl;
	f[u] = u;
	vis[u] = 1;
	for (int i = headt[u]; i != -1; i = te[i].next){
//		cout << i << endl;
		int v = te[i]. to;
		if (!vis[v]){
			tarjan(v);
			f[v] = u;
		}
	}
	for (int i = headq[u]; i != -1; i = qe[i].next){
//		cout << i << endl;
		int v = qe[i].to;
		int idx = qe[i].idx;
		if (vis[v]) ans[idx] = fin(v);
	}
}

void addt(int u, int v){
	te[tec].to = v;
	te[tec].next = headt[u];
	headt[u] = tec++;
}

void addq(int u, int v, int idx){
	qe[qec].to = v;
	qe[qec].idx = idx;
	qe[qec].next = headq[u];
	headq[u] = qec++;
}

int main(){
	int x, y;
	memset(vis, 0, sizeof(vis));
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 0; i <= n; i++) headt[i] = -1, headq[i] = -1;
	for (int i = 0; i < n - 1; i++){
		scanf("%d%d", &x, &y);
		addt(x, y);
		addt(y, x);
	}
	for (int i = 0; i < m; i++){
		scanf("%d%d", &x, &y);
		addq(x, y, i);
		addq(y, x, i);
	}
	tarjan(s);
	for (int i = 0; i < m; i++){
		printf("%d\n", ans[i]);
	}
}

b-a
我还没有学会写个人说明!
查看“b-a”的所有文章 →

Leave a Reply

Your email address will not be published. Required fields are marked *

相关推荐