\n 2\n <\/pre>\nSolution Process<\/h2>\n
To solve this problem, we will use the Union-Find data structure to organize the relationships between each node. We will follow these steps:<\/p>\n
Step 1: Initialize the Parent Array<\/h3>\n
Each node is initialized to have itself as its parent. In other words, we create a parent array and set each node to point to itself.<\/p>\n
\n parent = [0, 1, 2, 3, 4] # Initialized according to the number of nodes\n <\/pre>\nStep 2: Perform Union Operations<\/h3>\n
Based on the given edge information, we connect the nodes through Union operations. This combines connected sets into one.<\/p>\n
Step 3: Count Connected Sets Using Find Operations<\/h3>\n
By performing Find operations on each node, we check which set they belong to and count the number of unique root nodes before printing the result.<\/p>\n
Implementation<\/h2>\n
Now, let’s implement the above steps in Python code.<\/p>\n
\n class UnionFind:\n def __init__(self, size):\n self.parent = list(range(size))\n self.rank = [1] * size\n \n def find(self, p):\n if self.parent[p] != p:\n # Path compression\n self.parent[p] = self.find(self.parent[p])\n return self.parent[p]\n \n def union(self, p, q):\n rootP = self.find(p)\n rootQ = self.find(q)\n \n if rootP != rootQ:\n # Union by rank\n if self.rank[rootP] > self.rank[rootQ]:\n self.parent[rootQ] = rootP\n elif self.rank[rootP] < self.rank[rootQ]:\n self.parent[rootP] = rootQ\n else:\n self.parent[rootQ] = rootP\n self.rank[rootP] += 1\n\n # Usage Example\n def count_connected_components(n, edges):\n uf = UnionFind(n)\n \n # Perform Union with edge information\n for u, v in edges:\n uf.union(u, v)\n \n # Count the number of unique roots and return the number of connected components\n root_set = set(uf.find(i) for i in range(n))\n return len(root_set)\n\n # Input handling\n n = 5\n edges = [(0, 1), (1, 2), (3, 4)]\n print(count_connected_components(n, edges)) # Output: 2\n <\/pre>\nInterpreting Results<\/h2>\n
When executing the above code, it outputs 2. This indicates that there are two sets of nodes that are connected in the given graph.<\/p>\n
Time Complexity Analysis<\/h2>\n
When using Union-Find, the time complexity of each operation approaches O(\u03b1(n)), where \u03b1 is the inverse Ackermann function. Since this function grows extremely slowly, we can consider it to take close to constant time in practical terms.<\/p>\n
Conclusion<\/h2>\n
In this post, we examined the Union-Find data structure and methods for solving problems using it. We confirmed that Union-Find can efficiently solve complex connectivity problems, encouraging you to practice various applications.<\/p>\n
Thank you!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Hello! In this post, we will explore the Union-Find algorithm and solve algorithmic problems using it. The Union-Find is a very useful data structure for managing disjoint sets, providing the ability to quickly determine the connectivity of multiple items and to merge sets. What is Union-Find? Union-Find consists of two main functions: Union: An operation … \ub354 \ubcf4\uae30 “python coding test course, union find”<\/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":[145],"tags":[],"class_list":["post-33726","post","type-post","status-publish","format-standard","hentry","category-python-coding-test"],"yoast_head":"\npython coding test course, union find - \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\/33726\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"python coding test course, union find - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! In this post, we will explore the Union-Find algorithm and solve algorithmic problems using it. The Union-Find is a very useful data structure for managing disjoint sets, providing the ability to quickly determine the connectivity of multiple items and to merge sets. What is Union-Find? Union-Find consists of two main functions: Union: An operation … \ub354 \ubcf4\uae30 "python coding test course, union find"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33726\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:19:42+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:46:57+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\/33726\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33726\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"python coding test course, union find\",\"datePublished\":\"2024-11-01T09:19:42+00:00\",\"dateModified\":\"2024-11-01T11:46:57+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33726\/\"},\"wordCount\":458,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Python Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33726\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33726\/\",\"name\":\"python coding test course, union find - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:19:42+00:00\",\"dateModified\":\"2024-11-01T11:46:57+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33726\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33726\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33726\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"python coding test course, union find\"}]},{\"@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":"python coding test course, union find - \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\/33726\/","og_locale":"ko_KR","og_type":"article","og_title":"python coding test course, union find - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! In this post, we will explore the Union-Find algorithm and solve algorithmic problems using it. The Union-Find is a very useful data structure for managing disjoint sets, providing the ability to quickly determine the connectivity of multiple items and to merge sets. What is Union-Find? Union-Find consists of two main functions: Union: An operation … \ub354 \ubcf4\uae30 \"python coding test course, union find\"","og_url":"https:\/\/atmokpo.com\/w\/33726\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:19:42+00:00","article_modified_time":"2024-11-01T11:46:57+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\/33726\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33726\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"python coding test course, union find","datePublished":"2024-11-01T09:19:42+00:00","dateModified":"2024-11-01T11:46:57+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33726\/"},"wordCount":458,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Python Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33726\/","url":"https:\/\/atmokpo.com\/w\/33726\/","name":"python coding test course, union find - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:19:42+00:00","dateModified":"2024-11-01T11:46:57+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33726\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33726\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33726\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"python coding test course, union find"}]},{"@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\/33726","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=33726"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33726\/revisions"}],"predecessor-version":[{"id":33727,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33726\/revisions\/33727"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33726"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33726"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33726"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}