[백준/코틀린] 11724번: 연결 요소의 개수

링크

11724번: 연결 요소의 개수

풀이

연결 요소(Connected Component)란?
그래프에서 서로 연결된 정점들의 최대 집합을 말합니다.
같은 연결 요소 내의 정점들은 경로로 연결되어 있고, 다른 연결 요소와는 연결되지 않습니다.

아직 방문하지 않은 정점에서 DFS 또는 BFS를 시작할 때마다
새로운 연결 요소를 하나씩 발견하게 됩니다.
모든 정점을 순회하며 탐색 시작 횟수를 세면 연결 요소의 개수를 구할 수 있습니다.

코드

lateinit var graph: List<MutableList<Int>>
lateinit var visited: BooleanArray

fun dfs(start: Int) {
    val stack = ArrayDeque<Int>()

    visited[start] = true
    stack.addLast(start)
    while (stack.isNotEmpty()) {
        val current = stack.removeLast()

        graph[current].forEach {
            if (!visited[it]) {
                visited[it] = true
                stack.addLast(it)
            }
        }
    }
}

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    graph = List(n + 1) { mutableListOf() }
    visited = BooleanArray(n + 1)
    var ans = 0

    repeat(m) {
        val (u, v) = readln().split(" ").map { it.toInt() }

        graph[u] += v
        graph[v] += u
    }

    (1..n).forEach {
        if (!visited[it]) {
            dfs(it)
            ans++
        }
    }

    println(ans)
}