Java Coding Test Course, Counting the Number of Connected Components

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 connected components in the given undirected graph.

Input

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

Output

Output the number of connected components.

Example

    Input:
    5 3
    1 2
    2 3
    4 5

    Output:
    2

Problem Solving Strategy

To solve the problem, we will follow these steps:

  1. Represent the graph in the form of an adjacency list.
  2. Use DFS (Depth First Search) or BFS (Breadth First Search) to explore the connected components.
  3. Count the number of connected components during the exploration.

1. Graph Representation

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.

2. Exploration Using DFS

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.

3. Implementation and Result Derivation

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.

Java Code Implementation


import java.util.ArrayList;
import java.util.Scanner;

public class ConnectedComponents {
    static ArrayList[] graph;
    static boolean[] visited;
    static int count;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt(); // Number of vertices
        int m = scanner.nextInt(); // Number of edges
        
        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }
        
        count = 0; // Initialize connected components count
        
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs(i); // Execute DFS
                count++; // Increase count when a new connected component is found
            }
        }
        
        System.out.println(count); // Output the result
        scanner.close();
    }

    public static void dfs(int node) {
        visited[node] = true; // Mark the current node as visited
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor); // Explore adjacent nodes
            }
        }
    }
}

Code Explanation

The above Java code works as follows:

  1. Input the number of vertices n and edges m, and initialize the adjacency list graph.
  2. Input the edge information to construct the graph.
  3. Perform DFS for each vertex. If the vertex has not been visited, call DFS to visit all connected vertices.
  4. Increase the count of connected components each time DFS is called.
  5. Finally, output the number of connected components.

Complexity Analysis

The time complexity of this algorithm is O(n + m), where n is the number of vertices and m 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) additional space.

Conclusion

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.

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!