当前位置：首页 > news >正文

LCA(最近公共祖先)专题(不定期更新)

news 来源：原创 2024/4/29 4:55:29

Tarjan(离线)算法

　　思路：

　　　　　　1.任选一个点为根节点，从根节点开始。

　　　　　　2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。

　　　　　　3.若是v还有子节点，返回2，否则下一步。

　　　　　　4.合并v到u上。

　　　　　　5.寻找与当前点u有询问关系的点v。

　　　　　　6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。

1、POJ 1330 Nearest Common Ancestors

　　题意：给出一颗有根树(外向树)，再给出有向边。询问一次，求两点的最近公共祖先。

　　思路：最最基础的LCA题目，而且只询问一次。对于外向树，记录入度，入度为0的则为根。

　　①tarjan离线算法实现

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<memory.h>
 5 using namespace std;
 6 const int maxn = 10010;
 7 const int maxq = 10;
 8 vector<int> node[maxn];//邻接表
 9 int q1, q2, ans;
10 int n, qnum;
11 int index[maxn];//入度
12 int pre[maxn];//并查集
13 bool vis[maxn];//标记是否访问过
14 pair<int, int>queq[maxq];//保存查询顺序
15 int f[maxn];//保存临时祖先
16 int Find(int x)
17 {
18     int r = x;
19     while (pre[r] != r)
20     {
21         r = pre[r];
22     }
23     int i = x, j;
24     while (i != r)
25     {
26         j = pre[i];
27         if (j != r) pre[i] = r;
28         i = j;
29     }
30     return r;
31 }
32 void Join(int root, int child)
33 {
34     int rx = Find(root), ry = Find(child);
35     if (rx != ry) pre[child] = root;
36 }
37 void LCA(int root)
38 {
39     f[Find(root)] = root;
40     vis[root] = true;//标记被访问过
41     int sz = node[root].size();
42     for (int i = 0; i < sz; i++)
43     {//访问所有root子节点
44         if (!vis[node[root][i]])
45         {
46             LCA(node[root][i]);//继续往下遍历
47             Join(root, node[root][i]);//合并
48             f[Find(root)] = root;
49         }
50     }
51     if (q1 == root&&vis[q2]) ans = f[Find(q2)];
52     else if (q2 == root&&vis[q1]) ans = f[Find(q1)];
53 }
54 void Init()//初始化
55 {
56     for (int i = 0; i <= n; i++)
57     {
58         node[i].clear();
59         pre[i] = i;
60     }
61     memset(vis, 0, sizeof(vis));
62     memset(f, 0, sizeof(f));
63     memset(index, 0, sizeof(index));
64 }
65 int main()
66 {
67     int t;
68     scanf("%d", &t);
69     while (t--)
70     {
71         scanf("%d", &n);
72         Init();
73         for (int i = 1; i <= n - 1; i++)
74         {
75             int u, v;
76             scanf("%d%d", &u, &v);
77             node[u].push_back(v);//有向图
78             index[v]++;
79         }
80         scanf("%d%d", &q1, &q2);
81         int root = 1;
82         for (; root <= n; root++) if (!index[root]) break;//入度为0的为根
83         LCA(root);
84         printf("%d", ans);
85         printf("\n");
86     }
87     return 0;
88 }

tarjan离线算法

2、hdu 2874 Connections between cities

　　题意：给出一片森林(有多棵树)，询问若干次，如果两点是连通的，求其最短路径长度。

　　思路：tarjan离线算法

　　　　①要用边表来存储每条边和询问的点。用邻接表MLE。

　　　　②dis[]数组保存的是该点到根的距离(由于是树，所以每两点之间只有一条路径，且其为最短路径)。那么对于一棵树里的两点u,v，u、v之间的最短路径长度为dis[v]+dis[u]-2*dis[nf],nf为该两点的最近公共祖先。

  1 #include<iostream>
  2 #include<memory.h>
  3 #include<vector>
  4 using namespace std;
  5 int n, m, c;
  6 const int maxn = 10005;
  7 const int maxe = 10005;
  8 const int maxq = 1000005;
  9 //用边表来存各条边，邻接表MLE
 10 int Head[maxn];
 11 struct edge
 12 {
 13     int to;
 14     int len;
 15     int next;
 16 }eg[2*maxe];
 17 //用边表来存每次询问，邻接表MLE
 18 int qhead[maxn];
 19 struct qry
 20 {
 21     int to;
 22     int next;
 23 }qy[2*maxq];
 24 int ans[maxq];//存第i个询问的结果
 25 int dis[maxn];//存各棵树下结点到根的距离
 26 int vis[maxn];//是否访问标记，不为0时其值代表结点所在的树编号
 27 int pre[maxn];//并查集
 28 int f[maxn];//存祖先
 29 void Init()
 30 {
 31     for (int i = 0; i <= n; i++)
 32     {
 33         pre[i] = i;
 34     }
 35     memset(qhead, 0, sizeof(qhead));
 36     memset(qy, 0, sizeof(qy));
 37     memset(eg, 0, sizeof(eg));
 38     memset(Head, 0, sizeof(Head));
 39     memset(ans, 0, sizeof(ans));
 40     memset(dis, 0, sizeof(dis));
 41     memset(vis, 0, sizeof(vis));
 42     memset(f, 0, sizeof(f));
 43 }
 44 int Findf(int x)
 45 {
 46     int r = x;
 47     while (r != pre[r])
 48     {
 49         r = pre[r];
 50     }
 51     int i = x, j;
 52     while (i != r)
 53     {
 54         j = pre[i];
 55         pre[i] = r;
 56         i = j;
 57     }
 58     return r;
 59 }
 60 void Join(int x, int y)
 61 {
 62     int rx = Findf(x), ry = Findf(y);
 63     if (rx != ry) pre[x] = y;
 64 }
 65 void LCA(int rt, int k)
 66 {
 67     vis[rt] = k;
 68     f[rt] = rt;
 69     for (int i = Head[rt]; i!=0; i=eg[i].next)
 70     {
 71         int u = eg[i].to;
 72         if (!vis[u])
 73         {
 74             dis[u] = dis[rt] + eg[i].len;
 75             LCA(u, k);
 76             Join(u, rt);
 77             f[Findf(rt)] = rt;
 78         }
 79     }
 80     for (int i = qhead[rt]; i != 0; i = qy[i].next)
 81     {
 82         int v = qy[i].to;
 83         if (vis[v] && vis[v] == vis[rt])
 84         {
 85             ans[(i+1) / 2] = dis[rt] + dis[v] - 2 * dis[Findf(v)];
 86         }
 87         else ans[(i+1) / 2] = -1;
 88     }
 89 
 90 }
 91 int main()
 92 {
 93     while (~scanf("%d%d%d", &n, &m, &c))
 94     {
 95         Init();
 96         int cnt = 1;
 97         for (int i = 1; i <= m; i++)
 98         {
 99             int u, v, len;
100             scanf("%d%d%d", &u, &v, &len);
101             eg[cnt].to = v, eg[cnt].len = len,eg[cnt].next=Head[u],Head[u]=cnt;
102             cnt++;
103             eg[cnt].to = u, eg[cnt].len = len, eg[cnt].next = Head[v], Head[v] = cnt;
104             cnt++;
105         }
106         cnt = 1;
107         for (int i = 1; i <= c; i++)
108         {
109             int u, v;
110             scanf("%d%d", &u, &v);
111             qy[cnt].to = v, qy[cnt].next = qhead[u], qhead[u] = cnt;
112             cnt++;
113             qy[cnt].to = u, qy[cnt].next = qhead[v], qhead[v] = cnt;
114             cnt++;//这样保存(cnt+1)/2则为其询问编号
115         }
116         int k = 1;
117         for (int i = 1; i <= n; i++)
118         {
119             if (!vis[i])
120             {
121                 LCA(i, k);
122                 k++;
123             }
124         }
125         for (int i = 1; i <= c; i++)
126         {
127             if (ans[i] == -1) printf("Not connected\n");
128             else printf("%d\n", ans[i]);
129         }
130     }
131     return 0;
132 }

View Code

3、hdu 4547 CD操作

　　题意：从子目录到父目录需要一级一级向上，从父目录只需要一步就能到子目录。给出n-1个相差一级的<子目录，父目录>，询问m次从a目录到b目录的最小步数。

　　思路：tarjan离线算法

　　①由于目录名称为字符串，用string来存，建立映射，即为每个目录名称建立对应的唯一编号，之后用编号来进行对应处理。

　　②用边表存储每条有向边；用边表存储询问对(反着也要存一遍)

　　③dis[]数组保存的是该点到根的距离,每条有向边的长度为1.如果询问的序号i为奇数(没有反,从rt到v)，则ans[(i+1)/2]=dis[rt]-dis[rf]+(rf==v?0:1);否则表示从v到rt,则ans[(i+1)/2]=dis[v]-dis[rf]+(rf==rt?0:1).

此处rf为rt和v的最近公共祖先。

  1 #include<iostream>
  2 #include<memory.h>
  3 #include<vector>
  4 #include<map>
  5 #include<string>
  6 using namespace std;
  7 int n, m, c;
  8 map<string, int>mp;
  9 const int maxn = 100005;
 10 const int maxe = 100005;
 11 const int maxq = 100005;
 12 int in[maxn];
 13 //用边表来存各条边
 14 int Head[maxn];
 15 struct edge
 16 {
 17     int to;
 18     int len;
 19     int next;
 20 }eg[maxe];
 21 //用边表来存每次询问
 22 int qhead[maxn];
 23 struct qry
 24 {
 25     int to;
 26     int next;
 27 }qy[2 * maxq];
 28 int ans[maxq];//存第i个询问的结果
 29 int dis[maxn];//存结点到根的距离
 30 int vis[maxn];//是否访问标记
 31 int pre[maxn];//并查集
 32 int f[maxn];//存祖先
 33 void Init()
 34 {
 35     for (int i = 0; i <= n; i++)
 36     {
 37         pre[i] = i;
 38     }
 39     mp.clear();
 40     memset(in, 0, sizeof(in));
 41     memset(qhead, 0, sizeof(qhead));
 42     memset(qy, 0, sizeof(qy));
 43     memset(eg, 0, sizeof(eg));
 44     memset(Head, 0, sizeof(Head));
 45     memset(ans, 0, sizeof(ans));
 46     memset(dis, 0, sizeof(dis));
 47     memset(vis, 0, sizeof(vis));
 48     memset(f, 0, sizeof(f));
 49 }
 50 int Findf(int x)
 51 {
 52     int r = x;
 53     while (r != pre[r])
 54     {
 55         r = pre[r];
 56     }
 57     int i = x, j;
 58     while (i != r)
 59     {
 60         j = pre[i];
 61         pre[i] = r;
 62         i = j;
 63     }
 64     return r;
 65 }
 66 void Join(int x, int y)
 67 {
 68     int rx = Findf(x), ry = Findf(y);
 69     if (rx != ry) pre[x] = y;
 70 }
 71 void LCA(int rt)
 72 {
 73     vis[rt] = 1;
 74     f[rt] = rt;
 75     for (int i = Head[rt]; i != 0; i = eg[i].next)
 76     {
 77         int u = eg[i].to;
 78         if (!vis[u])
 79         {
 80             dis[u] = dis[rt] + eg[i].len;
 81             LCA(u);
 82             Join(u, rt);
 83             f[Findf(rt)] = rt;
 84         }
 85     }
 86     for (int i = qhead[rt]; i != 0; i = qy[i].next)
 87     {
 88         int v = qy[i].to;
 89         if (vis[v])
 90         {
 91             int rf = Findf(v);
 92             if(i%2==1)ans[(i+1)/2] = dis[rt] - dis[rf] + (v== rf ? 0 : 1);
 93             else ans[(i+1)/2] = dis[v] - dis[rf] + (rt == rf ? 0 : 1);
 94         }
 95     }
 96 
 97 }
 98 int main()
 99 {
100     int t;
101     scanf("%d", &t);
102     while (t--)
103     {
104         scanf("%d%d", &n, &m);
105         Init();
106         string a, b;
107         int k = 0;
108         for (int i = 1; i <= n-1; i++)
109         {
110             int u, v;
111             cin >> a >> b;
112             if (!mp[a]) mp[a] = ++k;
113             if (!mp[b]) mp[b] = ++k;
114             u = mp[b], v = mp[a];//从b到a
115             in[v]++;
116             eg[i].to = v, eg[i].len = 1, eg[i].next = Head[u], Head[u] = i;
117         }
118         int cnt = 1;
119         for (int i = 1; i <= m; i++)
120         {
121             int u, v;
122             cin >> a >> b;
123             u = mp[a], v = mp[b];//从a到b
124             qy[cnt].to = v, qy[cnt].next = qhead[u], qhead[u] = cnt;//奇数从a到b
125             cnt++;
126             qy[cnt].to = u, qy[cnt].next = qhead[v], qhead[v] = cnt;//偶数从b到a
127             cnt++;
128 
129         }
130         for (int i = 1; i <= k; i++)
131         {
132             if (!in[i])
133             {
134                 LCA(i);
135                 break;
136             }
137         }
138         for (int i = 1; i <=m; i++)
139         {
140             printf("%d\n", ans[i]);
141         }
142     }
143     return 0;
144 }

View Code

4、hdu 6115 Factory

　　题意：给出无向图，给出每个公司的子公司的位置，若干次询问两个公司之间的最短距离(即两个公司所有子公司之间的最短距离)。

　　思路：LCA在线ST算法模板。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include<vector>
  6 #include<map>
  7 #include<algorithm>
  8 using namespace std;
  9 //#pragma comment(linker, "/STACK:102400000,102400000") //不需要申请系统栈
 10 const int N = 100010;
 11 const int M = 30;
 12 int dp[2 * N][M];  //这个数组记得开到2*N，因为遍历后序列长度为2*n-1
 13 bool vis[N];
 14 struct edge
 15 {
 16     int u, v, w, next;
 17 }e[2 * N];
 18 int tot, head[N];
 19 inline void add(int u, int v, int w, int &k)
 20 {
 21     e[k].u = u; e[k].v = v; e[k].w = w;
 22     e[k].next = head[u]; head[u] = k++;
 23     u = u^v; v = u^v; u = u^v;
 24     e[k].u = u; e[k].v = v; e[k].w = w;
 25     e[k].next = head[u]; head[u] = k++;
 26 }
 27 int ver[2 * N], R[2 * N], first[N], dir[N];
 28 //ver:节点编号 R：深度 first：点编号位置 dir：距离
 29 void dfs(int u, int dep)
 30 {
 31     vis[u] = true; ver[++tot] = u; first[u] = tot; R[tot] = dep;
 32     for (int k = head[u]; k != -1; k = e[k].next)
 33         if (!vis[e[k].v])
 34         {
 35             int v = e[k].v, w = e[k].w;
 36             dir[v] = dir[u] + w;
 37             dfs(v, dep + 1);
 38             ver[++tot] = u; R[tot] = dep;
 39         }
 40 }
 41 void ST(int n)
 42 {
 43     for (int i = 1; i <= n; i++)
 44         dp[i][0] = i;
 45     for (int j = 1; (1 << j) <= n; j++)
 46     {
 47         for (int i = 1; i + (1 << j) - 1 <= n; i++)
 48         {
 49             int a = dp[i][j - 1], b = dp[i + (1 << (j - 1))][j - 1];
 50             dp[i][j] = R[a]<R[b] ? a : b;
 51         }
 52     }
 53 }
 54 //中间部分是交叉的。
 55 int RMQ(int l, int r)
 56 {
 57     int k = 0;
 58     while ((1 << (k + 1)) <= r - l + 1)
 59         k++;
 60     int a = dp[l][k], b = dp[r - (1 << k) + 1][k]; //保存的是编号
 61     return R[a]<R[b] ? a : b;
 62 }
 63 
 64 int LCA(int u, int v)
 65 {
 66     int x = first[u], y = first[v];
 67     if (x > y) swap(x, y);
 68     int res = RMQ(x, y);
 69     return ver[res];
 70 }
 71 vector<int>cp[N];
 72 int main()
 73 {
 74     int cas;
 75     scanf("%d", &cas);
 76     while (cas--)
 77     {
 78         int n,m, q, num = 0;
 79         scanf("%d%d", &n, &m);
 80         memset(head, -1, sizeof(head));
 81         memset(vis, false, sizeof(vis));
 82         for (int i = 1; i<n; i++)
 83         {
 84             int u, v, w;
 85             scanf("%d%d%d", &u, &v, &w);
 86             add(u, v, w, num);
 87         }
 88         tot = 0; dir[1] = 0;
 89         dfs(1, 1);
 90         /*printf("节点ver "); for(int i=1; i<=2*n-1; i++) printf("%d ",ver[i]); cout << endl;
 91         printf("深度R "); for(int i=1; i<=2*n-1; i++) printf("%d ",R[i]);   cout << endl;
 92         printf("首位first "); for(int i=1; i<=n; i++) printf("%d ",first[i]);    cout << endl;
 93         printf("距离dir "); for(int i=1; i<=n; i++) printf("%d ",dir[i]);      cout << endl;*/
 94         ST(2 * n - 1);
 95         for (int i = 1; i <= m; i++)
 96         {
 97             cp[i].clear();
 98             int g;
 99             scanf("%d", &g);
100             for (int j = 0; j < g; j++)
101             {
102                 int v;
103                 scanf("%d", &v);
104                 cp[i].push_back(v);
105             }
106         }
107         scanf("%d", &q);
108         
109         while (q--)
110         {
111             int u, v;
112             scanf("%d%d", &u, &v);
113             int ans = 0x3f3f3f3f;
114             for (int i = 0; i < cp[u].size(); i++)
115             {
116                 for (int j = 0; j < cp[v].size(); j++)
117                 {
118                     int uu = cp[u][i];
119                     int vv = cp[v][j];
120                     int lca = LCA(uu, vv);
121                     ans = min(ans, dir[uu] + dir[vv] - 2 * dir[lca]);
122                 }
123             }
124             printf("%d\n", ans);
125         }
126     }
127     return 0;
128 }