首页 > 代码库 > poj1330 Nearest Common Ancestors
poj1330 Nearest Common Ancestors
题意:
LCA裸题。
思路:
1. 朴素
2. 基于二分
3. 基于RMQ
实现:
1.
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 using namespace std; 6 7 vector<int> G[10005]; 8 int t, n, x, y; 9 int in[10005], parent[10005], depth[10005]; 10 11 void dfs(int v, int p, int d) 12 { 13 parent[v] = p; 14 depth[v] = d; 15 for (int i = 0; i < G[v].size(); i++) 16 { 17 if (G[v][i] != p) 18 dfs(G[v][i], v, d + 1); 19 } 20 } 21 22 void init(int root) 23 { 24 dfs(root, -1, 0); 25 } 26 27 int lca(int root, int x, int y) 28 { 29 while (depth[x] > depth[y]) 30 { 31 x = parent[x]; 32 } 33 while (depth[y] > depth[x]) 34 { 35 y = parent[y]; 36 } 37 while (x != y) 38 { 39 x = parent[x]; 40 y = parent[y]; 41 } 42 return x; 43 } 44 45 int main() 46 { 47 cin >> t; 48 while (t--) 49 { 50 cin >> n; 51 for (int i = 1; i <= n; i++) 52 { 53 G[i].clear(); 54 } 55 memset(depth, 0, sizeof(depth)); 56 memset(in, 0, sizeof(depth)); 57 memset(parent, 0, sizeof(parent)); 58 for (int i = 0; i < n - 1; i++) 59 { 60 scanf("%d %d", &x, &y); 61 G[x].push_back(y); 62 in[y]++; 63 } 64 int root = 0; 65 for (int i = 1; i <= n; i++) 66 { 67 if (!in[i]) 68 { 69 root = i; 70 break; 71 } 72 } 73 cin >> x >> y; 74 init(root); 75 cout << lca(root, x, y) << endl; 76 } 77 return 0; 78 }
2.
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 using namespace std; 6 7 const int MAX_LOG_N = 14; 8 9 vector<int> G[10005]; 10 int t, n, x, y; 11 int in[10005], parent[MAX_LOG_N][10005], depth[10005]; 12 13 void dfs(int v, int p, int d) 14 { 15 parent[0][v] = p; 16 depth[v] = d; 17 for (int i = 0; i < G[v].size(); i++) 18 { 19 if (G[v][i] != p) 20 dfs(G[v][i], v, d + 1); 21 } 22 } 23 24 void init(int root) 25 { 26 dfs(root, -1, 0); 27 for (int k = 0; k < MAX_LOG_N - 1; k++) 28 { 29 for (int i = 1; i <= n; i++) 30 { 31 if (parent[k][i] < 0) 32 { 33 parent[k + 1][i] = -1; 34 } 35 else 36 { 37 parent[k + 1][i] = parent[k][parent[k][i]]; 38 } 39 } 40 } 41 } 42 43 int lca(int root, int x, int y) 44 { 45 if (depth[x] > depth[y]) 46 swap(x, y); 47 for (int k = 0; k < MAX_LOG_N; k++) 48 { 49 if ((depth[y] - depth[x]) >> k & 1) 50 { 51 y = parent[k][y]; 52 } 53 } 54 if (x == y) 55 { 56 return x; 57 } 58 for (int k = MAX_LOG_N - 1; k >= 0; k--) 59 { 60 if (parent[k][x] != parent[k][y]) 61 { 62 x = parent[k][x]; 63 y = parent[k][y]; 64 } 65 } 66 return parent[0][y]; 67 } 68 69 int main() 70 { 71 cin >> t; 72 while (t--) 73 { 74 cin >> n; 75 for (int i = 1; i <= n; i++) 76 { 77 G[i].clear(); 78 } 79 memset(depth, 0, sizeof(depth)); 80 memset(in, 0, sizeof(depth)); 81 memset(parent, 0, sizeof(parent)); 82 for (int i = 0; i < n - 1; i++) 83 { 84 scanf("%d %d", &x, &y); 85 G[x].push_back(y); 86 in[y]++; 87 } 88 int root = 0; 89 for (int i = 1; i <= n; i++) 90 { 91 if (!in[i]) 92 { 93 root = i; 94 break; 95 } 96 } 97 cin >> x >> y; 98 init(root); 99 cout << lca(root, x, y) << endl; 100 } 101 return 0; 102 }
3.
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int MAXN = 10005; 9 vector<int> G[MAXN]; 10 int t, n, x, y; 11 int in[MAXN], depth[2 * MAXN - 1], id[MAXN], vs[2 * MAXN - 1]; 12 13 const int MAXM = 32768; 14 const int INF = 0x3f3f3f3f; 15 struct node 16 { 17 int index, d; 18 }; 19 node data[2 * MAXM - 1]; 20 21 void update(int k, int a) 22 { 23 int tmp = k; 24 k += n - 1; 25 data[k].index = tmp; 26 data[k].d = a; 27 while (k) 28 { 29 k = (k - 1) / 2; 30 if (data[2 * k + 1].d < data[2 * k + 2].d) 31 { 32 data[k].d = data[2 * k + 1].d; 33 data[k].index = data[2 * k + 1].index; 34 } 35 else 36 { 37 data[k].d = data[2 * k + 2].d; 38 data[k].index = data[2 * k + 2].index; 39 } 40 } 41 } 42 43 void rmq_init(int * depth, int k) 44 { 45 n = 1; 46 while (n < k) n <<= 1; 47 for (int i = 0; i < 2 * n; i++) 48 { 49 data[i].d = INF; 50 } 51 for (int i = 0; i < k; i++) 52 { 53 update(i, *(depth + i)); 54 } 55 } 56 57 node query(int a, int b, int k, int l, int r) 58 { 59 if (b <= l || a >= r) 60 { 61 node res; 62 res.index = -1; 63 res.d = INF; 64 return res; 65 } 66 if (l >= a && r <= b) 67 return data[k]; 68 node x = query(a, b, 2 * k + 1, l, (l + r) / 2); 69 node y = query(a, b, 2 * k + 2, (l + r) / 2, r); 70 if (x.d < y.d) 71 return x; 72 return y; 73 } 74 75 void dfs(int v, int p, int d, int & k) 76 { 77 id[v] = k; 78 vs[k] = v; 79 depth[k++] = d; 80 for (int i = 0; i < G[v].size(); i++) 81 { 82 if (G[v][i] != p) 83 { 84 dfs(G[v][i], v, d + 1, k); 85 vs[k] = v; 86 depth[k++] = d; 87 } 88 } 89 } 90 91 int init(int root) 92 { 93 int k = 0; 94 dfs(root, -1, 0, k); 95 rmq_init(depth, k); 96 return k; 97 } 98 99 int lca(int root, int x, int y) 100 { 101 node res = query(min(id[x], id[y]), max(id[x], id[y]) + 1, 0, 0, n); 102 return vs[res.index]; 103 } 104 105 int main() 106 { 107 cin >> t; 108 while (t--) 109 { 110 cin >> n; 111 for (int i = 1; i <= n; i++) 112 { 113 G[i].clear(); 114 } 115 memset(depth, 0x3f, sizeof(depth)); 116 memset(in, 0, sizeof(depth)); 117 memset(id, 0, sizeof(id)); 118 memset(vs, 0, sizeof(vs)); 119 for (int i = 0; i < n - 1; i++) 120 { 121 scanf("%d %d", &x, &y); 122 G[x].push_back(y); 123 in[y]++; 124 } 125 int root = 0; 126 for (int i = 1; i <= n; i++) 127 { 128 if (!in[i]) 129 { 130 root = i; 131 break; 132 } 133 } 134 int res = init(root); 135 cin >> x >> y; 136 cout << lca(root, x, y) << endl; 137 } 138 return 0; 139 }
总结:
还可以使用tarjan算法。
poj1330 Nearest Common Ancestors
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。