首页 > 代码库 > 最近公共祖先模版
最近公共祖先模版
LCA tarjan 的离线算法
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn = 40010; int first[maxn], head[maxn], cnt, sum; struct edge { int u, v, w, next; }e[maxn*2], qe[maxn], Q[maxn]; int ans[maxn]; int f[maxn], vis[maxn]; int d[maxn]; void AddEdge(int u, int v, int w) { e[cnt].u = u; e[cnt].v = v; e[cnt].w = w; e[cnt].next = first[u]; first[u] = cnt++; e[cnt].u = v; e[cnt].v = u; e[cnt].w = w; e[cnt].next = first[v]; first[v] = cnt++; } int find(int x) { if(f[x] != x) return f[x] = find(f[x]); return f[x]; } void LCA(int u, int k) { f[u] = u; d[u] = k; vis[u] = true; for(int i = first[u]; i != -1; i = e[i].next) { int v = e[i].v; if(vis[v]) continue; LCA(v, k + e[i].w); f[v] = u; } for(int i = head[u]; i != -1; i = qe[i].next) { int v = qe[i].v; if(vis[v]) { ans[qe[i].w] = find(v); } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。