Kotlin Coding Test, Counting the Number of Connected Components

Hello! Today, I am going to solve a coding test problem using Kotlin. The topic is “Counting the Number of Connected Components”. 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 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.

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 contain information about the edges. (Vertex A, Vertex B, 1 ≤ A, B ≤ N)

Output

  • Output the number of connected components.

Example Input

6 5
1 2
2 5
5 1
3 4
6 2

Example Output

2

Solution Process

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.

1. Graph Representation

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 empty list and add the connected vertices for each vertex. In Kotlin, we can use MutableList.

2. Implementing the DFS Function

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.

3. Connected Component Count

We call DFS for all vertices to count the number of connected components. If DFS is called, we increase the count.

Code Implementation

Now let’s implement the above process in code. Below is the code written in Kotlin.

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val graph = MutableList(n + 1) { mutableListOf() }

    for (i in 0 until m) {
        val (a, b) = readLine()!!.split(" ").map { it.toInt() }
        graph[a].add(b)
        graph[b].add(a)
    }

    val visited = BooleanArray(n + 1)
    var count = 0

    fun dfs(vertex: Int) {
        visited[vertex] = true
        for (neighbor in graph[vertex]) {
            if (!visited[neighbor]) {
                dfs(neighbor)
            }
        }
    }

    for (i in 1..n) {
        if (!visited[i]) {
            dfs(i)
            count++
        }
    }

    println(count)
}

4. Time Complexity Analysis

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.

Conclusion

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.

I hope to further solidify the theory through practice problems and work hard to prepare for coding tests. See you in the next lecture!