HDU 2874 /// tarjan离线求森林里两点的距离

题目大意：

在一个森林里 询问 u v 两点

若不能到达输出 "Not connected" 否则输出两点距离

https://blog.csdn.net/keyboarderqq/article/details/56842607

和求树上两点差不多

改变的是树上两点的vis标记改成了记录根节点

此时 继续搜时 判断vis未标记过 就改成了是否存在根节点

而 更新答案时 判断vis标记过 则改成了根节点是否与当前根节点相同

#include <bits/stdc++.h>

#define mem(i,j) memset(i,j,sizeof(i))

using namespace std;

const int N=1e4+, Q=1e6+;

struct EDGE {

    int to, w, nt;

}e[N<<], q[Q<<];

int head[N], tot, que[N], pos;

///和HDU2586一样的毒 询问开N 如果开Q会MLE

int fa[N], dis[N], root[N];

int n, m, t, ans[Q];

void init() {

    tot=; mem(head,);

    pos=; mem(que,);

    mem(root,); mem(ans,-);

}

void addE(int u,int v,int w) {

    e[tot].to=v, e[tot].w=w;

    e[tot].nt=head[u];

    head[u]=tot++;

}

void addQ(int u,int v,int w) {

    q[pos].to=v, q[pos].w=w;

    q[pos].nt=que[u];

    que[u]=pos++;

}

int getfa(int u) {

    if(fa[u]==u) return u;

    return fa[u]=getfa(fa[u]);

}

void Tarjan(int u,int rt) {

    fa[u]=u; root[u]=rt;

    for(int i=head[u];i;i=e[i].nt) {

        int v=e[i].to;

        if(!root[v]) {

            dis[v]=dis[u]+e[i].w;

            Tarjan(v,rt); fa[v]=u;

        }

    }

    for(int i=que[u];i;i=q[i].nt) {

        int v=q[i].to;

        if(root[v]==rt)

            ans[q[i].w]=dis[u]+dis[v]-*dis[getfa(v)];

    }

}

int main()

{

    while(~scanf("%d%d%d",&n,&m,&t)) {

        init();

        for(int i=;i<m;i++) {

            int u,v,w; scanf("%d%d%d",&u,&v,&w);

            addE(u,v,w); addE(v,u,w);

        }

        for(int i=;i<=t;i++) {

            int u,v; scanf("%d%d",&u,&v);

            addQ(u,v,i), addQ(v,u,i);

        }

        for(int i=;i<=n;i++)

            if(!root[i]) {

                dis[i]=;

                Tarjan(i,i);

            }

        for(int i=;i<=t;i++)

             if(ans[i]==-) puts("Not connected");

             else printf("%d\n",ans[i]);

    }

    return ;

}