{"id":33434,"date":"2024-11-01T09:16:27","date_gmt":"2024-11-01T09:16:27","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33434"},"modified":"2024-11-01T11:38:42","modified_gmt":"2024-11-01T11:38:42","slug":"java-coding-test-course-counting-the-number-of-connected-components","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33434\/","title":{"rendered":"Java Coding Test Course, Counting the Number of Connected Components"},"content":{"rendered":"

<\/p>\n

Problem Description<\/h2>\n

This is a problem to find the number of connected components in a given graph. A connected component refers to a subgraph in which there is a path between any two vertices. In other words, if two vertices are connected, they belong to the same connected component.<\/p>\n

Problem Definition<\/h3>\n

Output the number of connected components in the given undirected graph<\/strong>.<\/p>\n

Input<\/h3>\n

The first line contains the number of vertices n<\/code> (1 \u2264 n<\/code> \u2264 1000) and the number of edges m<\/code> (0 \u2264 m<\/code> \u2264 10000). The next m<\/code> lines provide the two endpoints of each edge u<\/code> and v<\/code>. u<\/code> and v<\/code> are distinct vertices, represented by integers from 1<\/code> to n<\/code>.<\/p>\n

Output<\/h3>\n

Output the number of connected components.<\/p>\n

Example<\/h2>\n
\n    Input:\n    5 3\n    1 2\n    2 3\n    4 5\n\n    Output:\n    2\n    <\/pre>\n
Problem Solving Strategy<\/h2>\n
To solve the problem, we will follow these steps:<\/p>\n
    \n
  1. Represent the graph in the form of an adjacency list.<\/li>\n
  2. Use DFS (Depth First Search) or BFS (Breadth First Search) to explore the connected components.<\/li>\n
  3. Count the number of connected components during the exploration.<\/li>\n<\/ol>\n
    1. Graph Representation<\/h3>\n
    We represent the undirected graph as an adjacency list. Each vertex stores a list of its connected vertices. In Java, this can be easily implemented using ArrayList<\/code>.<\/p>\n
    2. Exploration Using DFS<\/h3>\n
    After representing the graph, we perform DFS for each vertex to visit the connected vertices. We use an array to keep track of visited vertices to avoid visiting them again.<\/p>\n
    3. Implementation and Result Derivation<\/h3>\n
    We maintain a counter variable to count the total number of connected components, and we increase the count each time DFS starts at a new vertex.<\/p>\n
    Java Code Implementation<\/h2>\n
    \nimport java.util.ArrayList;\nimport java.util.Scanner;\n\npublic class ConnectedComponents {\n    static ArrayList[] graph;\n    static boolean[] visited;\n    static int count;\n\n    public static void main(String[] args) {\n        Scanner scanner = new Scanner(System.in);\n        \n        int n = scanner.nextInt(); \/\/ Number of vertices\n        int m = scanner.nextInt(); \/\/ Number of edges\n        \n        graph = new ArrayList[n + 1];\n        visited = new boolean[n + 1];\n        \n        for (int i = 1; i <= n; i++) {\n            graph[i] = new ArrayList<>();\n        }\n        \n        for (int i = 0; i < m; i++) {\n            int u = scanner.nextInt();\n            int v = scanner.nextInt();\n            graph[u].add(v);\n            graph[v].add(u);\n        }\n        \n        count = 0; \/\/ Initialize connected components count\n        \n        for (int i = 1; i <= n; i++) {\n            if (!visited[i]) {\n                dfs(i); \/\/ Execute DFS\n                count++; \/\/ Increase count when a new connected component is found\n            }\n        }\n        \n        System.out.println(count); \/\/ Output the result\n        scanner.close();\n    }\n\n    public static void dfs(int node) {\n        visited[node] = true; \/\/ Mark the current node as visited\n        for (int neighbor : graph[node]) {\n            if (!visited[neighbor]) {\n                dfs(neighbor); \/\/ Explore adjacent nodes\n            }\n        }\n    }\n}\n    <\/Integer><\/code><\/pre>\n
    Code Explanation<\/h2>\n
    The above Java code works as follows:<\/p>\n
      \n
    1. Input the number of vertices n<\/code> and edges m<\/code>, and initialize the adjacency list graph<\/code>.<\/li>\n
    2. Input the edge information to construct the graph.<\/li>\n
    3. Perform DFS for each vertex. If the vertex has not been visited, call DFS to visit all connected vertices.<\/li>\n
    4. Increase the count of connected components each time DFS is called.<\/li>\n
    5. Finally, output the number of connected components.<\/li>\n<\/ol>\n
      Complexity Analysis<\/h2>\n
      The time complexity of this algorithm is O(n + m)<\/code>, where n<\/code> is the number of vertices and m<\/code> is the number of edges. This is because all vertices and edges are visited once during the DFS. The space complexity also uses O(n + m)<\/code> additional space.<\/p>\n
      Conclusion<\/h2>\n
      The problem of finding the number of connected components can be solved using exploration algorithms such as DFS or BFS. This problem requires a deep understanding of graphs, and it is important to master accurate graph representation and exploration methodologies in the problem-solving process. By doing so, you can build a useful foundational knowledge for coding tests.<\/p>\n
      Through this tutorial, we have learned the basics of graph theory and how to find the number of connected components. Continue to practice various graph problems to improve your algorithm skills!<\/p>\n
      <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
      Problem Description This is a problem to find the number of connected components in a given graph. A connected component refers to a subgraph in which there is a path between any two vertices. In other words, if two vertices are connected, they belong to the same connected component. Problem Definition Output the number of … \ub354 \ubcf4\uae30 “Java Coding Test Course, Counting the Number of Connected Components”<\/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":[139],"tags":[],"class_list":["post-33434","post","type-post","status-publish","format-standard","hentry","category-java-coding-test"],"yoast_head":"\nJava 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\/33434\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Java Coding Test Course, Counting the Number of Connected Components - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Problem Description This is a problem to find the number of connected components in a given graph. A connected component refers to a subgraph in which there is a path between any two vertices. In other words, if two vertices are connected, they belong to the same connected component. Problem Definition Output the number of … \ub354 \ubcf4\uae30 "Java Coding Test Course, Counting the Number of Connected Components"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33434\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:16:27+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:38:42+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\/33434\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33434\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Java Coding Test Course, Counting the Number of Connected Components\",\"datePublished\":\"2024-11-01T09:16:27+00:00\",\"dateModified\":\"2024-11-01T11:38:42+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33434\/\"},\"wordCount\":450,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Java Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33434\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33434\/\",\"name\":\"Java 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:16:27+00:00\",\"dateModified\":\"2024-11-01T11:38:42+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33434\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33434\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33434\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Java 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":"Java 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\/33434\/","og_locale":"ko_KR","og_type":"article","og_title":"Java Coding Test Course, Counting the Number of Connected Components - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Problem Description This is a problem to find the number of connected components in a given graph. A connected component refers to a subgraph in which there is a path between any two vertices. In other words, if two vertices are connected, they belong to the same connected component. Problem Definition Output the number of … \ub354 \ubcf4\uae30 \"Java Coding Test Course, Counting the Number of Connected Components\"","og_url":"https:\/\/atmokpo.com\/w\/33434\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:16:27+00:00","article_modified_time":"2024-11-01T11:38:42+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\/33434\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33434\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Java Coding Test Course, Counting the Number of Connected Components","datePublished":"2024-11-01T09:16:27+00:00","dateModified":"2024-11-01T11:38:42+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33434\/"},"wordCount":450,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Java Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33434\/","url":"https:\/\/atmokpo.com\/w\/33434\/","name":"Java 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:16:27+00:00","dateModified":"2024-11-01T11:38:42+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33434\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33434\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33434\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Java 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\/33434","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=33434"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33434\/revisions"}],"predecessor-version":[{"id":33435,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33434\/revisions\/33435"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33434"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33434"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33434"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}