C++ Coding Test Course, Finding Lowest Common Ancestor 1

This course will cover the problem of finding the Lowest Common Ancestor (LCA) using C++ programming.
The lowest common ancestor refers to the deepest node that is an ancestor of both nodes. This problem is useful for understanding tree data structures and depth-first search (DFS).

Problem Description

Given a tree, you are to solve the problem of finding the lowest common ancestor of two nodes A and B.
It is assumed that the tree is not empty and that there are no duplicate nodes. The nodes are numbered starting from 1.

Input Format

N
A B
where N is the number of nodes, and A and B are the two nodes for which to find the lowest common ancestor.

The tree is given as follows.
M lines are given, consisting of a parent node and a child node, 
where each line represents parent P and child C in the format 'P C'.

Output Format

Print the node number of the lowest common ancestor of nodes A and B.

Example

Input

Output

Problem Analysis

In the given example, the tree can be represented as follows:

The topmost parent of nodes A (5) and B (3) is 4, which is the lowest common ancestor.
If nodes A and B are the same, that node itself will be the lowest common ancestor.

Algorithm Approach

Various algorithms exist for finding the lowest common ancestor, but here we will explain a method using depth-first search (DFS) and parent tracking.

1. Storing the Tree Structure

First, we will store the tree using an adjacency list. If we know the parent node, we construct the tree by adding child nodes to the list.

2. Storing Depth via DFS

This method records the depth of each node and traces the parent nodes to find the LCA.
While exploring each node, we keep track of the depth and also store the parent node.

3. Finding the LCA

By comparing the depths of nodes A and B, we lift the shallower node while tracking the parent nodes.
When the two nodes become equal, that node is the LCA.

C++ Code Implementation

Below is the algorithm code written in C++:


#include 
#include 
#include 

using namespace std;

vector tree[100001];
int parent[100001];
int depth[100001];

// Store depth and parent through DFS
void dfs(int node, int par, int dep) {
    parent[node] = par;
    depth[node] = dep;
    for (int child : tree[node]) {
        if (child != par) {
            dfs(child, node, dep + 1);
        }
    }
}

// Finding LCA of two nodes
int findLCA(int a, int b) {
    // Align depths
    while (depth[a] > depth[b]) {
        a = parent[a];
    }
    while (depth[b] > depth[a]) {
        b = parent[b];
    }

    // Finding LCA
    while (a != b) {
        a = parent[a];
        b = parent[b];
    }
    return a;
}

int main() {
    int N;
    cin >> N;

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // Store depth and parent information via DFS
    dfs(1, 0, 0);

    int A, B;
    cin >> A >> B;

    cout << findLCA(A, B) << endl;
    return 0;
}

Code Explanation

1. Tree Representation

According to the given input, the tree is represented in the form of an adjacency list.
Each parent-child relationship is stored for later reference during the DFS.

2. DFS Function

The dfs function receives the current node, parent node, and depth, storing the parent and depth of that node while traversing.
It only explores child nodes when they are not the same as the parent.

3. LCA Function

After adjusting the depths of the two nodes, the function climbs up through the parents to find the point where the two nodes become equal.
This point is the lowest common ancestor.

Conclusion

In this course, we explored the concept, approach, and C++ implementation of the lowest common ancestor problem.
This problem is very useful for understanding the basic concepts of tree data structures and frequently appears in various application problems.
To enhance your algorithm problem-solving skills, I encourage you to tackle this problem from various angles.