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

링크

11724번: 연결 요소의 개수

풀이

DFS 또는 BFS로 그래프의 모든 정점을 탐색하며 연결 요소의 개수를 셉니다.

코드

lateinit var graph: List<MutableList<Int>>
lateinit var visited: BooleanArray
val stack = ArrayDeque<Int>()

fun dfs(s: Int) {
    visited[s] = true
    stack.addLast(s)
    while (stack.isNotEmpty()) {
        val cur = stack.removeLast()

        graph[cur].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)
}