NanoApe's Blog

既是咸鱼又是辣鸡

【图论】离线Tarjan求LCA

NanoApe posted @ 2016年5月25日 09:48 in 蒟蒻不撕烤智熵何来 , 366 阅读

 

离线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序的右括号位置


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter