fork download
copy 
  1. /*
  2. 	LCA Tarjan --- POJ 1330.
  3. 	[调用方法]树存G(有向or无向).询问存进Q(无向).然后对树根root调用LCA(root)即可得出所有询问的答案.第i的询问对应第2i-1和2i-2条询问边.
  4. 	[注意]这里我为了方便把G和Q的结构放一块儿了.有时图的结果可能需要复杂一些,则要把G和Q分开(或者不分开,把两个人需要的属性都一起放起来,可以减少代码量,但会增加空间)
  5. */
  6. const int MAXV = 10005;
  7. const int MAXE = 10005;
  8. struct Gragh{
  9.     struct Gragh_Node{
  10.         int u, v;
  11.         int opp;
  12.         int next;
  13.         int res;        //存Query的结果
  14.     }arc[MAXE];
  15.     int cnt, head[MAXV];
  16.     void init(){
  17.         cnt = 0;
  18.         memset(head, -1, sizeof(head));
  19.     }
  20.     void d_insert(int u, int v){		//有向边
  21.         arc[cnt].u = u;
  22.         arc[cnt].v = v;
  23.         arc[cnt].res = 0;
  24.         arc[cnt].next = head[u];
  25.         head[u] = cnt ++;
  26.     }
  27.     void u_insert(int u, int v){		//无向边
  28.         arc[cnt].u = u;
  29.         arc[cnt].v = v;
  30.         arc[cnt].res = 0;
  31.         arc[cnt].next = head[u];
  32.         arc[cnt].opp = cnt + 1;
  33.         head[u] = cnt ++;
  34.         arc[cnt].u = v;
  35.         arc[cnt].v = u;
  36.         arc[cnt].res = 0;
  37.         arc[cnt].next = head[v];
  38.         arc[cnt].opp = cnt - 1;
  39.         head[v] = cnt ++;
  40.     }
  41. };
  42. struct Disjoint_Sets{
  43.     struct Sets{
  44.         int father, ranks;
  45.     }S[MAXV];
  46.     void Init(int n){
  47.         for (int i = 0; i <= n; i ++)
  48.             S[i].father = i, S[i].ranks = 0;
  49.     }
  50.     int Father(int x){
  51.         if (S[x].father == x){
  52.             return x;
  53.         }
  54.         else{
  55.             S[x].father = Father(S[x].father);     		//Path compression
  56.             return S[x].father;
  57.         }
  58.     }
  59.     bool Union(int x, int y){
  60.         int fx = Father(x), fy = Father(y);
  61.         if (fx == fy){
  62.             return false;
  63.         }
  64.         else{                                           //Rank merge
  65.             if (S[fx].ranks > S[fy].ranks){
  66.                 S[fy].father = fx;
  67.             }
  68.             else{
  69.                 S[fx].father = fy;
  70.                 if (S[fx].ranks == S[fy].ranks){
  71.                     ++ S[fy].ranks;
  72.                 }
  73.             }
  74.             return true;
  75.         }
  76.     }
  77. };
  78. struct LCA{
  79.     Gragh G, Q;         //G存图(树); Q存查询,可以把每个询问当成一个无向边存储
  80.     Disjoint_Sets DS;
  81.     int ancestor[MAXV];
  82.     int indegree[MAXV];
  83.     bool vis[MAXV];
  84.     void init(int n){
  85.         memset(ancestor,0,sizeof(ancestor));
  86.         memset(vis,0,sizeof(vis));
  87.         G.init();
  88.         Q.init();
  89.         DS.Init(n);
  90.     }
  91.     void insert_gragh(int u, int v){
  92.         G.d_insert(u, v);
  93.     }
  94.     void insert_query(int u, int v){
  95.         Q.u_insert(u, v);
  96.     }
  97.     void lca(int u){
  98.         ancestor[u] = u;
  99.         for (int i = G.head[u]; i != -1; i = G.arc[i].next){
  100.             int v = G.arc[i].v;
  101.             lca(v);
  102.             DS.Union(u, v);
  103.             ancestor[DS.Father(u)] = u;
  104.         }
  105.         vis[u] = 1;
  106.         for (int i = Q.head[u]; i != -1; i = Q.arc[i].next){
  107.             int v = Q.arc[i].v;
  108.             if (vis[v])
  109.                 Q.arc[i].res = ancestor[DS.Father(v)];
  110.                 Q.arc[Q.arc[i].opp].res = ancestor[DS.Father(v)];
  111.         }
  112.     }
  113.     void solve(int n){
  114.         memset(vis, 0, sizeof(vis));
  115.         memset(indegree, 0, sizeof(indegree));
  116.         for (int i = 0; i < G.cnt; i ++){
  117.             indegree[G.arc[i].v] ++;
  118.         }
  119.         for (int i = 1; i <= n; i ++){
  120.             if (indegree[i] == 0)
  121.                 lca(i);
  122.         }
  123.     }
  124. }L;
  125.  
  126. int main(){
  127.     //freopen("data.txt","r+",stdin);
  128.     int t, n;
  129.     scanf("%d",&t);
  130.     while(t --){
  131.         scanf("%d",&n);
  132.         L.init(n);
  133.         for (int i = 1; i < n; i ++){
  134.             int u,v;
  135.             scanf("%d %d",&u,&v);
  136.             L.insert_gragh(u, v);
  137.         }
  138.         int u,v;
  139.         scanf("%d %d",&u,&v);
  140.         L.insert_query(u, v);
  141.         L.solve(n);
  142.         printf("%d\n", L.Q.arc[1].res);     //第i个询问对应第2i-1条Query边
  143.     }
  144.     return 0;
  145. }
  146.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1pnjB7
LCA tarjan模板 //POJ 1330
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!