{"id":35074,"date":"2024-11-01T09:35:16","date_gmt":"2024-11-01T09:35:16","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=35074"},"modified":"2024-11-01T12:46:47","modified_gmt":"2024-11-01T12:46:47","slug":"%ec%bd%94%ed%8b%80%eb%a6%b0-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-counting-the-number-of-connected-components","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/35074\/","title":{"rendered":"Kotlin Coding Test, Counting the Number of Connected Components"},"content":{"rendered":"<div class=\"wp-block-post\">\n<p>Hello! Today, I am going to solve a coding test problem using Kotlin. The topic is &#8220;Counting the Number of Connected Components&#8221;. This problem requires an understanding of graph theory and DFS (Depth-First Search) or BFS (Breadth-First Search). Through this problem, we will expand our concepts about graphs and connected components.<\/p>\n<h2>Problem Description<\/h2>\n<p>Given the number of vertices N and the number of edges M, an undirected graph with N vertices is provided. Write a program to count the number of connected components in this graph. A connected component refers to a set of vertices that are connected to each other.<\/p>\n<p><strong>Input<\/strong><\/p>\n<ul>\n<li>The first line contains the number of vertices N (1 \u2264 N \u2264 1000) and the number of edges M (0 \u2264 M \u2264 10000).<\/li>\n<li>The next M lines contain information about the edges. (Vertex A, Vertex B, 1 \u2264 A, B \u2264 N)<\/li>\n<\/ul>\n<p><strong>Output<\/strong><\/p>\n<ul>\n<li>Output the number of connected components.<\/li>\n<\/ul>\n<h2>Example Input<\/h2>\n<pre><code>6 5\n1 2\n2 5\n5 1\n3 4\n6 2<\/code><\/pre>\n<h2>Example Output<\/h2>\n<pre><code>2<\/code><\/pre>\n<h2>Solution Process<\/h2>\n<p>To solve this problem, we can use DFS (or BFS) to explore all connected components of the graph. This way, we can visit each connected component once and increase the count. The entire process is as follows.<\/p>\n<h3>1. Graph Representation<\/h3>\n<p>First, we represent the graph using an adjacency list. An adjacency list maintains a list of connected vertices for each vertex. To do this, we create an <strong>empty list<\/strong> and add the connected vertices for each vertex. In Kotlin, we can use <strong>MutableList<\/strong>.<\/p>\n<h3>2. Implementing the DFS Function<\/h3>\n<p>We implement a function that explores the graph using DFS. This function visits a specific vertex and recursively visits all vertices connected to it. The visited vertices are marked to avoid duplicate visits later.<\/p>\n<h3>3. Connected Component Count<\/h3>\n<p>We call DFS for all vertices to count the number of connected components. If DFS is called, we increase the count.<\/p>\n<h3>Code Implementation<\/h3>\n<p>Now let&#8217;s implement the above process in code. Below is the code written in Kotlin.<\/p>\n<pre><code>fun main() {\n    val (n, m) = readLine()!!.split(\" \").map { it.toInt() }\n    val graph = MutableList(n + 1) { mutableListOf<int>() }\n\n    for (i in 0 until m) {\n        val (a, b) = readLine()!!.split(\" \").map { it.toInt() }\n        graph[a].add(b)\n        graph[b].add(a)\n    }\n\n    val visited = BooleanArray(n + 1)\n    var count = 0\n\n    fun dfs(vertex: Int) {\n        visited[vertex] = true\n        for (neighbor in graph[vertex]) {\n            if (!visited[neighbor]) {\n                dfs(neighbor)\n            }\n        }\n    }\n\n    for (i in 1..n) {\n        if (!visited[i]) {\n            dfs(i)\n            count++\n        }\n    }\n\n    println(count)\n}<\/int><\/code><\/pre>\n<h3>4. Time Complexity Analysis<\/h3>\n<p>The time complexity of this algorithm is O(N + M). Here, N is the number of vertices, and M is the number of edges. Hence, it is proportional to the time taken to visit the graph once and explore all edges.<\/p>\n<h2>Conclusion<\/h2>\n<p>Through this lecture, we have learned how to solve the problem of counting the number of connected components. Understanding and utilizing the basics of graph theory and DFS\/BFS is very important for coding tests. Solidifying the foundation of this algorithm will greatly help in solving various problems.<\/p>\n<p>I hope to further solidify the theory through practice problems and work hard to prepare for coding tests. See you in the next lecture!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Hello! Today, I am going to solve a coding test problem using Kotlin. The topic is &#8220;Counting the Number of Connected Components&#8221;. This problem requires an understanding of graph theory and DFS (Depth-First Search) or BFS (Breadth-First Search). Through this problem, we will expand our concepts about graphs and connected components. Problem Description Given the &hellip; <a href=\"https:\/\/atmokpo.com\/w\/35074\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Kotlin Coding Test, 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":[106],"tags":[],"class_list":["post-35074","post","type-post","status-publish","format-standard","hentry","category----en"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Kotlin Coding Test, 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\/35074\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Kotlin Coding Test, Counting the Number of Connected Components - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! Today, I am going to solve a coding test problem using Kotlin. The topic is &#8220;Counting the Number of Connected Components&#8221;. This problem requires an understanding of graph theory and DFS (Depth-First Search) or BFS (Breadth-First Search). Through this problem, we will expand our concepts about graphs and connected components. Problem Description Given the &hellip; \ub354 \ubcf4\uae30 &quot;Kotlin Coding Test, Counting the Number of Connected Components&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/35074\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:35:16+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T12:46:47+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\/35074\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35074\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Kotlin Coding Test, Counting the Number of Connected Components\",\"datePublished\":\"2024-11-01T09:35:16+00:00\",\"dateModified\":\"2024-11-01T12:46:47+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35074\/\"},\"wordCount\":436,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/35074\/\",\"url\":\"https:\/\/atmokpo.com\/w\/35074\/\",\"name\":\"Kotlin Coding Test, Counting the Number of Connected Components - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:35:16+00:00\",\"dateModified\":\"2024-11-01T12:46:47+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35074\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/35074\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/35074\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Kotlin Coding Test, 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":"Kotlin Coding Test, 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\/35074\/","og_locale":"ko_KR","og_type":"article","og_title":"Kotlin Coding Test, Counting the Number of Connected Components - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! Today, I am going to solve a coding test problem using Kotlin. The topic is &#8220;Counting the Number of Connected Components&#8221;. This problem requires an understanding of graph theory and DFS (Depth-First Search) or BFS (Breadth-First Search). Through this problem, we will expand our concepts about graphs and connected components. Problem Description Given the &hellip; \ub354 \ubcf4\uae30 \"Kotlin Coding Test, Counting the Number of Connected Components\"","og_url":"https:\/\/atmokpo.com\/w\/35074\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:35:16+00:00","article_modified_time":"2024-11-01T12:46:47+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\/35074\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/35074\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Kotlin Coding Test, Counting the Number of Connected Components","datePublished":"2024-11-01T09:35:16+00:00","dateModified":"2024-11-01T12:46:47+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/35074\/"},"wordCount":436,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/35074\/","url":"https:\/\/atmokpo.com\/w\/35074\/","name":"Kotlin Coding Test, Counting the Number of Connected Components - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:35:16+00:00","dateModified":"2024-11-01T12:46:47+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/35074\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/35074\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/35074\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Kotlin Coding Test, 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\/35074","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=35074"}],"version-history":[{"count":2,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35074\/revisions"}],"predecessor-version":[{"id":38092,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35074\/revisions\/38092"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=35074"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=35074"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=35074"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}