C++ Coding Test Course, Finding the Number of Connected Components

Hello! Today, we will explore one of the frequently occurring algorithm problems in C++ coding tests, which is “Counting the Number of Connected Components.” This problem will greatly help in understanding and implementing the important concept of ‘connected components’ in graph theory.

Problem Description

This is a problem of counting the number of connected components in a given undirected graph. A connected component refers to a set of vertices in a partial graph that are connected to each other. When there are edges between the vertices of the graph, all vertices that are directly or indirectly connected are considered to form one connected component. For example, let’s assume there is a graph as shown below.

This graph constitutes one connected component consisting of 1, 0, 2, and 3, and if there are independent vertices like the one shown below, the number of connected components would be two.

As illustrated, it can be classified into a connected component containing 1, 2, and 3, and a connected component containing 4.

Input Format

The first line contains the number of vertices N (1 ≤ N ≤ 1000) and the number of edges M (0 ≤ M ≤ N*(N-1)/2).
The next M lines represent the information for each edge, providing two vertices A and B, which indicates that vertices A and B are connected.

Output Format

Print the number of connected components.

Example

Input:
5 3
0 1
0 2
3 4

Output:
2

Solution

To solve this problem, we will approach it in the following manner.

1. Graph Representation

We use an adjacency list to represent the graph. We declare a vector to store connection information for each vertex and build the graph by inputting the information for M edges. This can be easily implemented using vector from C++ STL.

#include <iostream>
#include <vector>

using namespace std;

vector> graph;
void addEdge(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
}

2. Using DFS or BFS

To count the number of connected components, it is necessary to explore all vertices of the graph. The traversal method we choose is Depth-First Search (DFS). This will allow us to visit all vertices connected to the current vertex. We change the state of visited vertices from ‘unvisited’ to ‘visited’ to avoid duplicate visits.

void dfs(int node, vector& visited) {
    visited[node] = true; // Mark the current node as visited
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

3. Implementing Key Variables and Logic

We declare a variable components to count the number of connected components and explore all vertices one by one. Each time we visit a vertex, we call DFS and increment components beforehand. At this stage, by checking all vertices, we can determine the total number of connected components.

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b);
    }

    vector visited(n, false);
    int components = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, visited);
            components++; // A new connected component found
        }
    }

    cout << components << endl; // Output the result
    return 0;
}

Complete Code

#include <iostream>
#include <vector>

using namespace std;

vector> graph;

// Function to add an edge
void addEdge(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
}

// DFS function
void dfs(int node, vector& visited) {
    visited[node] = true; // Mark the current node as visited
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b);
    }

    vector visited(n, false);
    int components = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, visited);
            components++; // A new connected component found
        }
    }

    cout << components << endl; // Output the result
    return 0;
}

Algorithm Review

Now, through this problem, we learned how to represent a graph and explore connected components using DFS. The complexity of the algorithm is as follows:

Time Complexity: O(N + M), where N is the number of vertices and M is the number of edges.
Space Complexity: O(N + M), which requires space to store the graph and to record whether vertices have been visited.

Tips for Problem Solving

Before solving the problem, try sketching out how the graph is constructed. This will make understanding the problem easier.
Using BFS to find each connected component is also a good approach. Since BFS explores in level order, it can be advantageous in certain problems.
Depending on the situation, there may also be problems analyzing the size or structure of each component besides just counting the connected components, so it’s good to practice graph traversal.

This concludes the explanation of the “Counting the Number of Connected Components” problem. I hope this lecture was helpful, and I look forward to exploring various algorithms and problems together in the future. Thank you!