Tarjan求lca

https://vjudge.net/problem/POJ-1330

是到水的题，简单点在于其只需求一对lca即可，这是比较简单的。

主要看了以下blog

http://blog.csdn.net/hnust_xiehonghao/article/details/9109295

要点在于

1.用并查集维护。

2.必须是离线的，在线不行。

3.存边可以用vector，比较方便，毕竟边不多。

*4.rank可以实现启发式并查集，可以优化一些时间。

5.anse数组是存祖先的，因为并查集维护，所以只需一步更新即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<string>
 6 #include<cstring>
 7 #include<vector>
 8 const int size=10007;
 9 
10 int n,f[size],anse[size],in[size],rank[size],vis[size];
11 using namespace std;
12 vector<int> node[size],que[size];
13 void init();
14 int find(int num);
15 void conbine(int aa,int bb);
16 void lca(int root)
17 {
18     int i,sz;
19     anse[root]=root;
20     sz=node[root].size();
21     for (int i=0;i<sz;i++)
22     {
23     //    if (fa!=node[root][i])
24     //    {
25             lca(node[root][i]);
26             conbine(root,node[root][i]);
27             anse[find(node[root][i])]=root;
28     //    }
29     }
30     vis[root]=1;
31     sz=que[root].size();
32     for (int i=0;i<sz;i++)
33     {
34         if (vis[que[root][i]])
35         {
36             printf("%d
",anse[find(que[root][i])]);
37             return;
38         }
39     }
40 }
41 int main()
42 {
43     int cas,i;
44     scanf("%d",&cas);
45     while (cas--)
46     {
47         int x,y;
48         scanf("%d",&n);
49         init();
50         for (int i=1;i<=n-1;i++)
51         {
52             scanf("%d%d",&x,&y);
53             node[x].push_back(y); 
54             in[y]++;
55         }
56         scanf("%d%d",&x,&y);
57         que[x].push_back(y);
58         que[y].push_back(x);
59         for (y=1;y<=n;y++)
60         {
61             if (in[y]==0) break;
62         }
63         lca(y);
64     }
65 }
66 void init()
67 {
68     int i;
69     for (int i=1;i<=n;i++)
70     {
71         node[i].clear();
72         que[i].clear();
73         f[i]=i;
74         rank[i]=1;
75     }
76     memset(vis,0,sizeof(vis));
77     memset(in,0,sizeof(in));
78     memset(anse,0,sizeof(anse));
79 }
80 int find(int num)
81 {
82     if (f[num]!=num) f[num]=find(f[num]);
83     return f[num];
84 }
85 void conbine(int aa,int bb)
86 {
87     int x=find(aa),y=find(bb);
88     if (x==y) return;
89     if (rank[x]<=rank[y])
90     {
91         f[x]=y;
92         rank[y]+=rank[x];
93     }
94     else
95     {
96         f[y]=x;
97         rank[x]+=rank[y];
98     }
99 }

求在线算法要用倍增lca