Resource:
লোয়েস্ট কমন অ্যানসেস্টর
Lowest Common Ancestor, Binary Lifting and HLD
copsiitbhu.co.in
Lowest Common Ancestor - O(N−−√) and O(logN) with O(N) preprocessing
Lowest Common Ancestor - Binary Lifting
Lowest Common Ancestor - Farach-Colton and Bender Algorithm
Solve RMQ (Range Minimum Query) by finding LCA (Lowest Common Ancestor)
Lowest Common Ancestor - Tarjan's off-line algorithm
topcoder
Lowest Common Ancestor
CF
Lowest Common Ancestor in a Binary Search Tree.
[Tutorial] Searching Binary Indexed Tree in O(log(N)) using Binary Lifting
CF blog
Youtube Video:
Gaurav Sen
Rachit jain
TusharRoy
Algorithms Live
ACM Advanced Training 2018 - Lecture 2-2 - LCA and Sparse Table
Problem:
Problems
LCA problems
Codechef
E-maxx blog problem list
LCA SOLUTION
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// lca using sparse table - O(nlogn). | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| int n, u, v; | |
| int dp[maxn][18], depth[maxn]; | |
| vector<int> graph[maxn]; | |
| void dfs(int u, int parent) | |
| { | |
| dp[u][0] = parent; | |
| for (auto v : graph[u]) { | |
| if (v == parent) continue; | |
| depth[v] = depth[u] + 1; | |
| dfs(v, u); | |
| } | |
| } | |
| int lca(int u, int v) | |
| { | |
| if (depth[u] < depth[v]) swap(u, v); | |
| for (int k = 17; k >= 0; k--) { | |
| if (depth[u] - (1 << k) >= depth[v]) { | |
| u = dp[u][k]; | |
| } | |
| } | |
| if (u == v) return u; | |
| for (int k = 17; k >= 0; k--) { | |
| if (dp[u][k] != dp[v][k]) { | |
| u = dp[u][k]; | |
| v = dp[v][k]; | |
| } | |
| } | |
| return dp[u][0]; | |
| } | |
| int main() | |
| { | |
| FASTIO | |
| ///* | |
| //double start_time = clock(); | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int T; | |
| //cin >> T; | |
| T = 1; | |
| for (int cs = 1; cs <= T; cs++) { | |
| scanf("%d", &n); | |
| for (int i = 1; i < n; i++) { | |
| scanf("%d %d", &u, &v); | |
| graph[u].push_back(v); | |
| graph[v].push_back(u); | |
| } | |
| memset(dp, -1, sizeof dp); | |
| dfs(1, -1); | |
| for (int k = 1; k <= 17; k++) { | |
| for (int u = 1; u <= n; u++) { | |
| if (dp[u][k - 1] == -1)continue; | |
| dp[u][k] = dp[dp[u][k - 1]][k - 1]; | |
| } | |
| } | |
| } | |
| int q; | |
| scanf("%d", &q); | |
| while (q--) { | |
| int u, v; | |
| scanf("%d %d", &u, &v); | |
| printf("lca (%d,%d) = %d\n", u, v, lca(u, v)); | |
| } | |
| //double end_time = clock(); | |
| //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); | |
| return 0; | |
| } |
No comments:
Post a Comment