{"id":34316,"date":"2024-11-01T09:26:46","date_gmt":"2024-11-01T09:26:46","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34316"},"modified":"2024-11-01T10:57:44","modified_gmt":"2024-11-01T10:57:44","slug":"c-coding-test-course-finding-lowest-common-ancestor-1","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34316\/","title":{"rendered":"C++ Coding Test Course, Finding Lowest Common Ancestor 1"},"content":{"rendered":"

<\/p>\n

\n This course will cover the problem of finding the Lowest Common Ancestor (LCA) using C++ programming.
\n 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).\n<\/p>\n

Problem Description<\/h2>\n

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

Input Format<\/h3>\n
\nN\nA B\nwhere N is the number of nodes, and A and B are the two nodes for which to find the lowest common ancestor.\n\nThe tree is given as follows.\nM lines are given, consisting of a parent node and a child node, \nwhere each line represents parent P and child C in the format 'P C'.\n<\/pre>\n
Output Format<\/h3>\n
\nPrint the node number of the lowest common ancestor of nodes A and B.\n<\/pre>\n
Example<\/h2>\n
Input<\/h3>\n
\n7\n4 5\n4 6\n5 3\n6 2\n1 4\n1 7\n<\/pre>\n
Output<\/h3>\n
\n4\n<\/pre>\n
Problem Analysis<\/h2>\n
\n    In the given example, the tree can be represented as follows:\n<\/p>\n
\n        1\n       \/ \\\n      4   7\n     \/ \\\n    5   6\n   \/     \\\n  3       2\n<\/pre>\n
\n    The topmost parent of nodes A (5) and B (3) is 4, which is the lowest common ancestor.
\n    If nodes A and B are the same, that node itself will be the lowest common ancestor.\n<\/p>\n
Algorithm Approach<\/h2>\n
\n    Various algorithms exist for finding the lowest common ancestor, but here we will explain a method using depth-first search (DFS) and parent tracking.\n<\/p>\n
1. Storing the Tree Structure<\/h3>\n
\n    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.\n<\/p>\n
2. Storing Depth via DFS<\/h3>\n
\n    This method records the depth of each node and traces the parent nodes to find the LCA.
\n    While exploring each node, we keep track of the depth and also store the parent node.\n<\/p>\n
3. Finding the LCA<\/h3>\n
\n    By comparing the depths of nodes A and B, we lift the shallower node while tracking the parent nodes.
\n    When the two nodes become equal, that node is the LCA.\n<\/p>\n
C++ Code Implementation<\/h2>\n
\n    Below is the algorithm code written in C++:\n<\/p>\n
\n#include \n#include \n#include \n\nusing namespace std;\n\nvector tree[100001];\nint parent[100001];\nint depth[100001];\n\n\/\/ Store depth and parent through DFS\nvoid dfs(int node, int par, int dep) {\n    parent[node] = par;\n    depth[node] = dep;\n    for (int child : tree[node]) {\n        if (child != par) {\n            dfs(child, node, dep + 1);\n        }\n    }\n}\n\n\/\/ Finding LCA of two nodes\nint findLCA(int a, int b) {\n    \/\/ Align depths\n    while (depth[a] > depth[b]) {\n        a = parent[a];\n    }\n    while (depth[b] > depth[a]) {\n        b = parent[b];\n    }\n\n    \/\/ Finding LCA\n    while (a != b) {\n        a = parent[a];\n        b = parent[b];\n    }\n    return a;\n}\n\nint main() {\n    int N;\n    cin >> N;\n\n    for (int i = 0; i < N - 1; i++) {\n        int u, v;\n        cin >> u >> v;\n        tree[u].push_back(v);\n        tree[v].push_back(u);\n    }\n\n    \/\/ Store depth and parent information via DFS\n    dfs(1, 0, 0);\n\n    int A, B;\n    cin >> A >> B;\n\n    cout << findLCA(A, B) << endl;\n    return 0;\n}\n<\/int><\/algorithm><\/vector><\/iostream><\/code><\/pre>\n
Code Explanation<\/h2>\n
1. Tree Representation<\/h3>\n
\n    According to the given input, the tree is represented in the form of an adjacency list.
\n    Each parent-child relationship is stored for later reference during the DFS.\n<\/p>\n
2. DFS Function<\/h3>\n
\nThe dfs<\/code> function receives the current node, parent node, and depth, storing the parent and depth of that node while traversing.
\n    It only explores child nodes when they are not the same as the parent.\n<\/p>\n
3. LCA Function<\/h3>\n
\n    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.
\n    This point is the lowest common ancestor.\n<\/p>\n
Conclusion<\/h2>\n
\n    In this course, we explored the concept, approach, and C++ implementation of the lowest common ancestor problem.
\n    This problem is very useful for understanding the basic concepts of tree data structures and frequently appears in various application problems.
\n    To enhance your algorithm problem-solving skills, I encourage you to tackle this problem from various angles.\n<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
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 … \ub354 \ubcf4\uae30 “C++ Coding Test Course, Finding Lowest Common Ancestor 1”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[111],"tags":[],"class_list":["post-34316","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials-2"],"yoast_head":"\nC++ Coding Test Course, Finding Lowest Common Ancestor 1 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34316\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Finding Lowest Common Ancestor 1 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"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 … \ub354 \ubcf4\uae30 "C++ Coding Test Course, Finding Lowest Common Ancestor 1"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34316\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:26:46+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:57:44+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34316\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34316\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Finding Lowest Common Ancestor 1\",\"datePublished\":\"2024-11-01T09:26:46+00:00\",\"dateModified\":\"2024-11-01T10:57:44+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34316\/\"},\"wordCount\":443,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34316\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34316\/\",\"name\":\"C++ Coding Test Course, Finding Lowest Common Ancestor 1 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:26:46+00:00\",\"dateModified\":\"2024-11-01T10:57:44+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34316\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34316\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34316\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ Coding Test Course, Finding Lowest Common Ancestor 1\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C++ Coding Test Course, Finding Lowest Common Ancestor 1 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34316\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Finding Lowest Common Ancestor 1 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"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 … \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Finding Lowest Common Ancestor 1\"","og_url":"https:\/\/atmokpo.com\/w\/34316\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:26:46+00:00","article_modified_time":"2024-11-01T10:57:44+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34316\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34316\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Finding Lowest Common Ancestor 1","datePublished":"2024-11-01T09:26:46+00:00","dateModified":"2024-11-01T10:57:44+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34316\/"},"wordCount":443,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34316\/","url":"https:\/\/atmokpo.com\/w\/34316\/","name":"C++ Coding Test Course, Finding Lowest Common Ancestor 1 - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:26:46+00:00","dateModified":"2024-11-01T10:57:44+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34316\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34316\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34316\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ Coding Test Course, Finding Lowest Common Ancestor 1"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34316","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34316"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34316\/revisions"}],"predecessor-version":[{"id":34317,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34316\/revisions\/34317"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34316"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34316"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34316"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}