poj 1330 Nearest Common Ancestors

http://poj.org/problem?id=1330
이것 은 tarjian 오프라인 버 전 입 니 다.
한 아버지의 모든 아이들 에 게우 리 는 모두 Lca 로 돌아 갔다.현재 점 이 물 어 볼 두 점 중 하나 이 고 다른 하 나 는 이미 방문 했다 면.출력 만.
방법 1:Tarjan 오프라인 알고리즘 은 오프라인 알고리즘 을 배 울 때 먼저 심도 있 는 검색 을 공 고 히 해 야 합 니 다.그리고 Tarjan 오프라인 알고리즘 은 깊이 있 는 우선 검색 을 바탕 으로 합 니 다.우 리 는 뿌리 부터 아래로 검색 하고 한 노드 를 찾 을 때 이 노드 의 모든 하위 노드 가 방 문 했 는 지 여 부 를 먼저 판단 합 니 다.만약 에 이미 방문 했다 면...이 노드 가 점 안의 하 나 를 물 었 는 지 판단 하고 만약 에 그렇다면 이에 대응 하 는 그 점 이 이미 방문 한 적 이 있 는 지 판단 한다.만약 에 방문 한 적 이 있다 면 그들의 최근 공공 조상 은 이미 방문 한 그 노드 의 현재 노드 이 고 다른 노드 가 방문 하지 않 았 다 면 심도 있 는 검색 을 계속 할 것 이다.
 

 1 #include<iostream>

 2 #include<string.h>

 3 #include<algorithm>

 4 #include<stdio.h>

 5 #define maxn 12000

 6 #include<vector>

 7 using namespace std;

 8 int father[maxn];

 9 int  visit[maxn];

10 int  root[maxn];

11 vector<int>node[maxn];

12 int st,en;

13 int n;

14 void init()

15 {

16     cin>>n;

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

18     {

19         father[i]=i;

20         root[i]=1;

21         visit[i]=0;

22         node[i].clear();

23     }

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

25     {

26         int a,b;

27         cin>>a>>b;

28         node[a].push_back(b);

29         root[b]=0;

30     }

31     cin>>st>>en;

32 }

33 

34 int find(int a)

35 {

36        if(father[a]!=a)

37        {

38            father[a]=find(father[a]);

39        }

40        return father[a];

41 }

42 void Union(int a,int b)

43 {

44     int fa=find(a);

45     int fb=find(b);

46     if(fa!=fb)

47     father[fb]=fa;

48 }

49 

50 void Lca(int parent)

51 {

52     for(int i=0;i<node[parent].size();i++)

53     {

54         Lca(node[parent][i]);

55         Union(parent,node[parent][i]);

56     }

57     visit[parent]=1;

58     if(parent==st&&visit[en])

59     {

60         cout<<find(en)<<endl;

61         return ;

62     }

63     else

64     if(parent==en&&visit[st])

65     {

66         cout<<find(st)<<endl;

67         return ;

68     }

69 }

70 

71 int main()

72 {

73     int test;

74     cin>>test;

75     for(int i=1;i<=test;i++)

76     {

77         init();

78 

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

80             if(root[i])

81             {

82 

83                 Lca(i);

84                 break;

85             }

86     }

87     //system("pause");

88     return 0;

89 }

 
 이게 온라인 버 전이 에 요.

#include<iostream>

#include<string.h>

#include<stdio.h>

#include<algorithm>

#include<vector>

#include<math.h>

#define maxn 10005

using namespace std;

vector<int>node[maxn];

int indegree[maxn];

int E[maxn*2+2];

int R[maxn];

int D[maxn*2+2];

int dp[maxn*2+2][100];

int n;

int st;

int en;

int p;

void init()

{

    cin>>n;

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

    {

        node[i].clear();

        indegree[i]=0;

        }

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

    {

    int a,b;

    cin>>a>>b;

    node[a].push_back(b);

    indegree[b]++;

    }

    p=0;

    cin>>st>>en;

}



void dfs(int root,int deep)

{

    p++;

    E[p]=root;

    D[p]=deep;

    R[root]=p;

    for(int i=0;i<node[root].size();i++)

    {

        dfs(node[root][i],deep+1);

        p++;

        E[p]=root;

        D[p]=deep;

    }

}

int min(int a,int b)

{

    return D[a]<D[b]?a:b;

}



void  Rmq(int a[],int num)

{

    memset(dp,0,sizeof(dp));

    for(int i=1;i<num;i++)

        dp[i][0]=i;

    int k=log((double)(num-1))/log(2.0);

    for(int j=1;j<=k;j++)

        for(int i=1;i+(1<<j)-1<num;i++)

        {

  dp[i][j]=D[dp[i][j-1]]<D[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];

        }

}



int Lca(int a[],int st,int en)

{

   int k=log(double(en-st+1))/log(2.0);

   return D[dp[st][k]]<D[dp[en-(1<<k)+1][k]]?dp[st][k]:dp[en-(1<<k)+1][k];

}

int main()

{

    int test;

    cin>>test;

    for(int i=1;i<=test;i++)

    {

        init();

        int root;

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

                   if(!indegree[i])

        {root=i;break;}

        dfs(root,0);

        Rmq(D,2*n);



        if(R[st]<R[en])

            cout<<E[Lca(D,R[st],R[en])]<<endl;

        else

            cout<<E[Lca(D,R[en],R[st])]<<endl;

    }

    system("pause");

    return 0;

}