【图论】离线Tarjan求LCA
NanoApe
posted @ 2016年5月25日 09:48
in 蒟蒻不撕烤智熵何来
, 1370 阅读
离线Tarjan求LCA
int H[maxn];
int Find(int x){return H[x]==x?x:(H[x]=Find(H[x]));}
void tarjan(int x)
{
H[x]=x; travel(x) if (p->y!=h[x]) tarjan(p->y), H[p->y]=x;
while (q[tot+1].k && q[tot+1].x==x) tot++, q[tot].z=Find(q[tot].y);
}
int main()
{
rep(i, 1, m) if (q[i].k && pos[q[i].x]<pos[q[i].y]) swap(q[i].x,q[i].y);
sort(q+1, q+1+m, cmpz); tot=0; tarjan(1);
}
其中pos数组是dfs序的右括号位置
评论 (0)
NanoApe
ENE>.<~
计数器
152912
分类
搜索
听听看？
最新留言
最新评论
链接
RSS
