{"id":34536,"date":"2024-11-01T09:29:07","date_gmt":"2024-11-01T09:29:07","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34536"},"modified":"2024-11-01T11:40:51","modified_gmt":"2024-11-01T11:40:51","slug":"javascript-coding-test-course-counting-the-number-of-connected-components","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34536\/","title":{"rendered":"JavaScript Coding Test Course, Counting the Number of Connected Components"},"content":{"rendered":"<article>\n<header>\n<p>In this course, we will explore the problem of &#8216;Counting the Number of Connected Components&#8217;, which is frequently presented in coding tests, and explain the algorithmic approach to solve it in detail. We will help you become familiar with JavaScript through in-depth learning with various examples.<\/p>\n<\/header>\n<section>\n<h2>Problem Description<\/h2>\n<p>This problem involves counting the number of connected components in a given undirected graph. An undirected graph consists of vertices (v) and edges (e) and represents the connectivity between vertices. That is, if there is an edge between two vertices, then these two vertices are directly connected. The connected components of a graph refer to a set of vertices that cannot be connected further. In this problem, there can be multiple sets, and the vertices within each set can reach each other but cannot reach vertices in other sets. For example, consider the following graph.<\/p>\n<pre>\n          0 --- 1     3 --- 4\n                |\n                2\n        <\/pre>\n<p>In this graph, there are two connected components: {0, 1, 2} and {3, 4}. Therefore, the number of connected components is 2.<\/p>\n<\/section>\n<section>\n<h2>Input Format<\/h2>\n<p>The function takes two parameters:<\/p>\n<ul>\n<li><strong>n<\/strong>: Number of vertices (0 \u2264 n \u2264 1000)<\/li>\n<li><strong>edges<\/strong>: A list of edges, where each edge is an array consisting of the vertex numbers. Example: <code>[[0,1], [1,2], [3,4]]<\/code><\/li>\n<\/ul>\n<\/section>\n<section>\n<h2>Output Format<\/h2>\n<p>Returns the number of connected components.<\/p>\n<\/section>\n<section>\n<h2>Examples<\/h2>\n<pre>\n          Input: n = 5, edges = [[0,1], [1,2], [3,4]]\n          Output: 2\n\n          Input: n = 6, edges = [[0,1], [0,2], [1,3]]\n          Output: 3\n        <\/pre>\n<\/section>\n<section>\n<h2>Solution Method<\/h2>\n<p>To calculate the number of connected components, we can use the DFS (Depth First Search) algorithm. DFS starts from one vertex and explores adjacent vertices deeply, visiting unvisited vertices. By utilizing this algorithm, we can traverse the graph and identify connected components. The steps to implement this are as follows:<\/p>\n<ol>\n<li><strong>Graph Creation:<\/strong> Convert the graph from the information of vertices and edges into an adjacency list format.<\/li>\n<li><strong>Create a Visited Array:<\/strong> Create an array to check if each vertex has been visited.<\/li>\n<li><strong>Implement DFS:<\/strong> Use a recursive function to implement DFS traversal, checking all vertices connected to each vertex upon visiting it.<\/li>\n<li><strong>Count Connected Components:<\/strong> Visit all vertices, increasing the count of connected components every time a new starting vertex is discovered.<\/li>\n<\/ol>\n<\/section>\n<section>\n<h2>JavaScript Code Implementation<\/h2>\n<pre>\n            <code>\n            function countConnectedComponents(n, edges) {\n                \/\/ Convert the graph to an adjacency list\n                const graph = Array.from({length: n}, () => []);\n                edges.forEach(([u, v]) => {\n                    graph[u].push(v);\n                    graph[v].push(u);\n                });\n\n                const visited = new Array(n).fill(false);\n                let count = 0;\n\n                function dfs(node) {\n                    visited[node] = true;\n                    for (const neighbor of graph[node]) {\n                        if (!visited[neighbor]) {\n                            dfs(neighbor);\n                        }\n                    }\n                }\n\n                for (let i = 0; i < n; i++) {\n                    if (!visited[i]) {\n                        dfs(i);\n                        count++; \/\/ Increase count every time a new connected component is found\n                    }\n                }\n\n                return count;\n            }\n\n            \/\/ Example execution\n            console.log(countConnectedComponents(5, [[0,1],[1,2],[3,4]])); \/\/ Output: 2\n            console.log(countConnectedComponents(6, [[0,1],[0,2],[1,3]])); \/\/ Output: 3\n            <\/code>\n        <\/pre>\n<\/section>\n<section>\n<h2>Complexity Analysis<\/h2>\n<p>The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges. This is due to the fact that we visit all vertices and edges in the graph. The space complexity is also O(V), which includes the space used to store the visited array and the graph.<\/p>\n<\/section>\n<section>\n<h2>Conclusion<\/h2>\n<p>In this course, we have implemented an algorithm to count the number of connected components using JavaScript. Graph theory is a very important topic in coding tests, and it is crucial to practice problems related to it thoroughly to build your skills. We hope this helps deepen your understanding through various examples and fosters your own algorithmic thinking.<\/p>\n<\/section>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>In this course, we will explore the problem of &#8216;Counting the Number of Connected Components&#8217;, which is frequently presented in coding tests, and explain the algorithmic approach to solve it in detail. We will help you become familiar with JavaScript through in-depth learning with various examples. Problem Description This problem involves counting the number of &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34536\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;JavaScript Coding Test Course, Counting the Number of Connected Components&#8221;<\/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":[141],"tags":[],"class_list":["post-34536","post","type-post","status-publish","format-standard","hentry","category-javascript-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>JavaScript Coding Test Course, Counting the Number of Connected Components - \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\/34536\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"JavaScript Coding Test Course, Counting the Number of Connected Components - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"In this course, we will explore the problem of &#8216;Counting the Number of Connected Components&#8217;, which is frequently presented in coding tests, and explain the algorithmic approach to solve it in detail. We will help you become familiar with JavaScript through in-depth learning with various examples. Problem Description This problem involves counting the number of &hellip; \ub354 \ubcf4\uae30 &quot;JavaScript Coding Test Course, Counting the Number of Connected Components&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34536\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:29:07+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:40:51+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=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34536\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34536\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"JavaScript Coding Test Course, Counting the Number of Connected Components\",\"datePublished\":\"2024-11-01T09:29:07+00:00\",\"dateModified\":\"2024-11-01T11:40:51+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34536\/\"},\"wordCount\":455,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Javascript Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34536\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34536\/\",\"name\":\"JavaScript Coding Test Course, Counting the Number of Connected Components - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:29:07+00:00\",\"dateModified\":\"2024-11-01T11:40:51+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34536\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34536\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34536\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"JavaScript Coding Test Course, Counting the Number of Connected Components\"}]},{\"@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":"JavaScript Coding Test Course, Counting the Number of Connected Components - \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\/34536\/","og_locale":"ko_KR","og_type":"article","og_title":"JavaScript Coding Test Course, Counting the Number of Connected Components - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"In this course, we will explore the problem of &#8216;Counting the Number of Connected Components&#8217;, which is frequently presented in coding tests, and explain the algorithmic approach to solve it in detail. We will help you become familiar with JavaScript through in-depth learning with various examples. Problem Description This problem involves counting the number of &hellip; \ub354 \ubcf4\uae30 \"JavaScript Coding Test Course, Counting the Number of Connected Components\"","og_url":"https:\/\/atmokpo.com\/w\/34536\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:29:07+00:00","article_modified_time":"2024-11-01T11:40:51+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":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34536\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34536\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"JavaScript Coding Test Course, Counting the Number of Connected Components","datePublished":"2024-11-01T09:29:07+00:00","dateModified":"2024-11-01T11:40:51+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34536\/"},"wordCount":455,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Javascript Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34536\/","url":"https:\/\/atmokpo.com\/w\/34536\/","name":"JavaScript Coding Test Course, Counting the Number of Connected Components - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:29:07+00:00","dateModified":"2024-11-01T11:40:51+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34536\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34536\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34536\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"JavaScript Coding Test Course, Counting the Number of Connected Components"}]},{"@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\/34536","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=34536"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34536\/revisions"}],"predecessor-version":[{"id":34537,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34536\/revisions\/34537"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34536"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34536"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34536"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}