Daily LeetCode Challenge - 2316. Count Unreachable Pairs of Nodes in an Undirected Graph

Problem From.
https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/

오늘 문제는 각 노드가 연결되어있는 edges 배열이 주어졌을때, 각 노드에서 서로 연결되어있지 않은 경로가 몇개인지 반환하는 문제였다.

이 문제는 DFS 를 통해서 해결할 수 있었는데, 처음에 0 의 노드에서 출발하여 각 노드의 끝까지 탐색하면서, 각 노드까지 연결되어있지 않은 수를 모두 세서 더해준다. 그런 다음에 마지막에 2로 나누어서 중복되어 있느 경우의 수를 빼주면 답을 얻을 수 있었다.

class Solution {

  fun countPairs(n: Int, edges: Array<IntArray>): Long {
    val g = List(n) {mutableListOf<Int>()}
    for ((a, b) in edges) {
      g[a].add(b)
      g[b].add(a)
    }

    val visited = BooleanArray(n)
    
    fun dfs(node: Int): Long {
      if (visited[node]) return 0
      visited[node] = true
      var res = 1L
      for (next in g[node])
        res += dfs(next)
      return res
    }
    
    var res = 0L
    for (i in 0 until n) {
      val groupSize = dfs(i)
      val unreachables = n - groupSize
      res += groupSize * unreachables      
    }
    return res / 2L
  }

}