// Using binary lifting to solve LCA problem with a tree structure #include<cstring> #include<iostream>
constint MAXN = 1005; constint LOG = 20;
int tree[MAXN][MAXN]; // Tree structure using adjacency matrix int child_count[MAXN];// Number of children for each node int depth[MAXN]; // Depth of each node int up[MAXN][LOG]; // up[i][j] represents the 2^j-th ancestor of node i
// Add an edge to the tree voidadd_edge(int u, int v){ tree[u][child_count[u]++] = v;// Add v as a child of u tree[v][child_count[v]++] = u;// Add u as a child of v (undirected tree) }
// DFS preprocessing to fill the `up` and `depth` arrays voiddfs(int u, int parent){ up[u][0] = parent;// Direct parent node for (int i = 1; i < LOG; ++i) { up[u][i] = up[up[u][i - 1]][i - 1];// Binary lifting }
// Traverse all children of the current node for (int i = 0; i < child_count[u]; ++i) { int v = tree[u][i]; if (v != parent) { depth[v] = depth[u] + 1; dfs(v, u); } } }
// Compute the LCA of two nodes intlca(int u, int v){ // Ensure u is the deeper node if (depth[u] < depth[v]) { std::swap(u, v); }
// Lift u to the same depth as v for (int i = LOG - 1; i >= 0; --i) { if (depth[u] - (1 << i) >= depth[v]) { u = up[u][i]; } }
// If u and v are the same, return the result if (u == v) { return u; }
// Lift u and v simultaneously until their parents are the same for (int i = LOG - 1; i >= 0; --i) { if (up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } }
// Return the LCA return up[u][0]; }
intmain(){ memset(tree, 0, sizeof(tree)); // Initialize the tree memset(child_count, 0, sizeof(child_count));// Initialize child counts
classTree { private: std::vector<std::vector<int>> adjList; // Adjacency list representation of the tree std::vector<int> dfsOrder; // Stores the DFS order
// Helper function for DFS traversal voiddfs(int node, int parent){ dfsOrder.push_back(node); // Add the current node to the DFS order (entering the node)
// Visit all children of the current node for (int child : adjList[node]) { if (child != parent) { // Avoid revisiting the parent node dfs(child, node); } }
dfsOrder.push_back(node); // Add the current node to the DFS order again (leaving the node) }
public: // Constructor to initialize the tree with n nodes Tree(int n) { adjList.resize(n + 1); // Nodes are 1-indexed }
// Add an edge to the tree voidaddEdge(int u, int v){ adjList[u].push_back(v); adjList[v].push_back(u); // Since it's an undirected tree }
// Perform DFS and return the DFS order std::vector<int> getDFSOrder(int root){ dfsOrder.clear(); // Clear any previous DFS order dfs(root, -1); // Start DFS from the root node return dfsOrder; } };
intmain(){ // Create a tree with 7 nodes Tree tree(7);
// Add edges to the tree tree.addEdge(1, 2); tree.addEdge(1, 3); tree.addEdge(2, 4); tree.addEdge(2, 5); tree.addEdge(3, 6); tree.addEdge(3, 7);
// Get the DFS order starting from node 1 std::cout << "DFS Order (with enter and leave) starting from node 1:" << std::endl; std::vector<int> dfsOrder = tree.getDFSOrder(1);
// Print the DFS order for (int node : dfsOrder) { std::cout << node << " "; } std::cout << std::endl;
return0; }
1 2
DFS Order (with enter and leave) starting from node 1: 12445523667731
// Another implementation of the LCA problem using Euler Tour and Sparse Table #include<cmath> #include<iostream> #include<vector>
usingnamespace std;
classEulerTourLCA { private: vector<vector<int>> adj;// Adjacency list representation of the tree vector<int> euler; // Euler tour order vector<int> depth; // Depth of each node vector<int> firstOccur; // First occurrence of each node in the Euler tour vector<vector<int>> st; // Sparse table (stores indices) int n; // Number of nodes
// Recursive function to generate Euler tour, depth, and first occurrence voiddfs(int u, int parent, int currentDepth){ firstOccur[u] = euler.size();// Record the first occurrence of the node euler.push_back(u); // Add the current node to the Euler tour depth[u] = currentDepth; // Record the depth of the node
for (int v : adj[u]) { if (v != parent) { dfs(v, u, currentDepth + 1); euler.push_back(u);// Add the current node again when backtracking } } }
// Build the sparse table (preprocess for range minimum query) voidbuildSparseTable(){ int m = euler.size(); int logM = log2(m) + 1; st.resize(m, vector<int>(logM));
// Initialize the first column (interval length = 1) for (int i = 0; i < m; ++i) { st[i][0] = i; }
// Fill the sparse table using dynamic programming for (int j = 1; (1 << j) <= m; ++j) { for (int i = 0; i + (1 << j) - 1 < m; ++i) { int mid = i + (1 << (j - 1)); if (depth[euler[st[i][j - 1]]] < depth[euler[st[mid][j - 1]]]) { st[i][j] = st[i][j - 1]; } else { st[i][j] = st[mid][j - 1]; } } } }
// Query the index of the node with the minimum depth in the range [l, r] intqueryMinIndex(int l, int r){ if (l > r) swap(l, r); int k = log2(r - l + 1); int mid = r - (1 << k) + 1;
// Tarjan's offline LCA algorithm implementation classTarjanLCA { private: vector<vector<int>> adj; vector<vector<pair<int, int>>> queries; unordered_map<int, int> lcaResult; vector<bool> visited; vector<int> ancestor; // Maps each node to its current ancestor in the tree
voiddfs(int node, int parent_node, disjointSet &ds){ visited[node] = true;
// Traverse all children for (int neighbor : adj[node]) { if (neighbor == parent_node) continue; dfs(neighbor, node, ds); // Merge child's set into current node's set int root_node = ds.Find(node); int root_neighbor = ds.Find(neighbor); ds.Union(root_node, root_neighbor); // Update ancestor of the new root to current node int new_root = ds.Find(root_node); ancestor[new_root] = node; }
// Process all queries associated with this node for (auto &q : queries[node]) { int v = q.first; int idx = q.second;
if (visited[v]) { int root = ds.Find(v); // Get the representative of v's set lcaResult[idx] = ancestor[root]; // Use the stored ancestor } } }
public: TarjanLCA(int n) : adj(n), visited(n, false), queries(n), ancestor(n) { for (int i = 0; i < n; ++i) { ancestor[i] = i; // Initialize each node's ancestor to itself } }
voidaddEdge(int u, int v){ adj[u].push_back(v); adj[v].push_back(u); }
voidaddQuery(int u, int v, int idx){ queries[u].push_back({v, idx}); queries[v].push_back({u, idx}); }
voidcomputeLCA(int root, int queryCount){ disjointSet ds(adj.size()); dfs(root, -1, ds);
cout << "\nComputed LCA results:\n"; for (int i = 0; i < queryCount; ++i) { if (lcaResult.find(i) != lcaResult.end()) { cout << "LCA of query[" << i << "] is " << lcaResult[i] << endl; } else { cout << "LCA of query[" << i << "] is not found!" << endl; } } } };