Tarjan LCA

强连通

   迷宫城堡

  Proving Equivalences

 Equivalent Sets

  Summer Holiday

  Intelligence System

  The King’s Problem

  Hawk-and-Chicken

  Cactus 仙人掌图

 

[双连通]:

2242 考研路茫茫——空调教室  双联通缩点+树形DP

2460 Network 边双连通

3849 By Recognizing These Guys, We Find Social Networks Useful  双连通求桥

3896 Greatest TC  双连通

 The war  边双连通

3394 Railway 双连通求块

[LCA]:

2586 How far away ？

2874 Connections between cities

3078 Network

3830 Checkers

 Simple Path 

参考Vendetta：

     需要补充的是vis可以在访问到节点时就标记，也可以在访问完其子孙后再标记，区别在于前者可以查询a和b的关系以及b和a的关系，而后者只能查询b和a的关系（假设先访问a），但既然是无向图，答案是一样的，目测放前面可能更强大。

HDU2586
#include<cstdio>

#include<cstring>

#include<cstring>

#include<iostream>

int const MAX = ;

struct Edge

{

    int id, val;

    int next;

}e[ * MAX];

int n, m, cnt;

int x[MAX], y[MAX], z[MAX];

int fa[MAX], dist[MAX], pre[MAX];

bool vis[MAX];

void _add(int u, int v, int w)

{

    e[cnt].id = u;

    e[cnt].val = w;

    e[cnt].next = pre[v];

    pre[v] = cnt++;

}

int Find(int x)

{

    return x == fa[x] ? x : fa[x] = Find(fa[x]);

}

void tarjan(int k)

{

    vis[k]=true;

    fa[k]=k;

    for(int i=pre[k];i;i=e[i].next){

        if(!vis[e[i].id]){

            dist[e[i].id]=dist[k]+e[i].val;

            tarjan(e[i].id);

            fa[e[i].id] = k;

        }

    }

    //vis[k]=true;

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

        if(x[i]==k&&vis[y[i]])

            z[i]=Find(y[i]);

    }

}

int main()

{

    int T,u,v,w;

    scanf("%d",&T);

    while(T--){

        scanf("%d %d", &n, &m);

        cnt=;

        memset(pre,,sizeof(pre));

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

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

            _add(u,v,w);

            _add(v,u,w);

        }

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

            x[i]=y[i]=z[i]=;

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

            scanf("%d %d",&x[i],&y[i]);

        memset(vis, false, sizeof(vis));

        dist[] = ;

        tarjan();

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

            printf("%d\n",dist[x[i]] + dist[y[i]] -  * dist[z[i]]);

    }

}

HDU2874

#include <iostream>

#include <vector>

#include <stack>

#include <cstring>

#include <cstdio>

#include <memory.h>

#include<vector>

using namespace std;

int Laxt[],Next[],To[],Len[];

int Laxt2[],Next2[],To2[],ans[];

bool vis[];

int cnt,cnt2;

int dis[],fa[];

void _update()

{

    memset(Laxt,-,sizeof(Laxt));

    memset(Laxt2,-,sizeof(Laxt2));

    memset(vis,false,sizeof(vis));

    cnt=cnt2=;

}

void _add(int u,int v,int d){

    Next[cnt]=Laxt[u];

    Laxt[u]=cnt;

    To[cnt]=v;

    Len[cnt++]=d;

}

void _add2(int u,int v){

    Next2[cnt2]=Laxt2[u];

    Laxt2[u]=cnt2;

    To2[cnt2++]=v;

    Next2[cnt2]=Laxt2[v];

    Laxt2[v]=cnt2;

    To2[cnt2++]=u;

}

int _findfa(int v){

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

    return fa[v]=_findfa(fa[v]);

}

void _tarjan(int v)

{

    vis[v]=true;fa[v]=v;

    for(int i=Laxt[v];i!=-;i=Next[i]){

        if(!vis[To[i]]){

            dis[To[i]]=dis[v]+Len[i];

            _tarjan(To[i]);

            fa[To[i]]=v;

        }

    }

    for(int i=Laxt2[v];i!=-;i=Next2[i]){

        if(vis[To2[i]]){

            int tmp=_findfa(To2[i]);

            if(dis[To2[i]]!=-)

              ans[i/]=dis[v]+dis[To2[i]]-*dis[tmp];

        }

    }

}

int main()

{

    int n,m,c,i,x,y,z;

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

           _update();

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

                scanf("%d%d%d",&x,&y,&z);

                _add(x,y,z);

                _add(y,x,z);

           }

           for(i=;i<c;i++){

                scanf("%d%d",&x,&y);

                _add2(x,y);

           }

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

                if(!vis[i]){

                  memset(dis,-,sizeof(dis));

                  dis[i]=;

                  _tarjan(i);

                }

             }

               for(i=;i<c;i++)

               if(ans[i]==-) printf("Not connected\n");

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

      }

      return ;

}