LAB REPORT 04
Title: Finding Lowest Common Ancesotr
Course title: Algorithms-II Laboratory
Course code: CSE-257
nd
2 Year 2 Semester Examination 2023
nd
Date of Submission: 16/01/2024
Submitted to-
Mohammad Ashraful Islam
Assistant Professor
Md. Masum Bhuiyan
Lecturer
Department of Computer Science and Engineering
Jahangirnagar University
Savar, Dhaka-1342
Sl Class Roll Exam Roll Name
01 381 210901 Shahed Annam
Department of Computer Science and Engineering
Jahangirnagar University
Savar, Dhaka, Bangladesh
Source Code:
#include<bits/stdc++.h>
using namespace std; int findLCA(int u, int v) {
const int M = 100005; if (depth[u] < depth[v]) {
const int N = 20; swap(u, v);
vector<int> tree[M]; }
int depth[M]; int log = log2(depth[u]) + 1;
int parent[M][N];
void dfs(int node, int par, int d) { for (int i = log; i >= 0; --i) {
depth[node] = d; if (depth[u] - (1 << i) >=
par depth[v]) {
ent[node][0] = par; u = parent[u][i];
}
for (int i = 0; i < }
tree[node].size(); ++i) {
int child = tree[node][i]; if (u == v) {
if (child != par) { return u;
dfs(child, node, d + 1); }
}
} for (int i = log; i >= 0; --i) {
} if (parent[u][i] != -1 &&
void buildSparseTable(int n) { parent[u][i] != parent[v][i]) {
for (int j = 1; (1 << j) < n; u = parent[u][i];
++j) { v = parent[v][i];
for (int i = 1; i <= n; ++i) }
{ }
if (parent[i][j - 1] !=
-1) { return parent[u][0];
parent[i][j] = }
parent[parent[i][j - 1]][j - 1];
}
}
}
}
int main() dfs(1, -1, 0);
{ buildSparseTable(n);
int n,q; while (q--) {
cin >> n>>q; int u, v;
for (int i = 1; i < n; ++i) { cin >> u >> v;
int u, v; int lca = findLCA(u, v);
cin >> u >> v; cout << "LCA of " << u << "
tree[u].push_back(v); and " << v << " is: " << lca << endl;
tree[v].push_back(u); }
} return 0;
}
Output: