LeetCode Entry

1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

19.08.2023 hard 2023 kotlin

List of list of must-have edges and list of optional edges for Minimum Weight Minimum Spanning Tree

1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree hard blog post substack

image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/313

Problem TLDR

List of list of must-have edges and list of optional edges for Minimum Weight Minimum Spanning Tree

Intuition

Use hints.

Minimum Spanning Tree can be obtained by sorting edges and adding not connected one-by-one using Union-Find

After we found target minimum weight, we can check how each node contributes: if removing the node increases the target, the node is a must-have. Also, if force using node in a spanning tree doesn’t change the target, node is optional.

Approach

  • careful with the sorted order of indices, returned positions must be in initial order
  • check if spanning tree is impossible to make, by checking if all nodes are connected

Complexity

  • Time complexity: \(O(E^2 + EV)\), sorting edges takes ElogE, then cycle E times algorithm of E+V

  • Space complexity: \(O(E + V)\), E for sorted edges, V for Union-Find array

Code


    fun findCriticalAndPseudoCriticalEdges(n: Int, edges: Array<IntArray>): List<List<Int>> {
      val sorted = edges.indices.sortedWith(compareBy({ edges[it][2] }))
      fun minSpanTreeW(included: Int = -1, excluded: Int = -1): Int {
        val uf = IntArray(n) { it }
        fun find(x: Int): Int = if (x == uf[x]) x else find(uf[x]).also { uf[x] = it }
        fun union(ind: Int): Int {
          val (a, b, w) = edges[ind]
          return if (find(a) == find(b)) 0 else w.also { uf[find(b)] = find(a) }
        }
        return ((if (included < 0) 0 else union(included)) + sorted
          .filter { it != excluded }.map { union(it) }.sum()!!)
          .takeIf { (0 until n).all { find(0) == find(it) } } ?: Int.MAX_VALUE
      }
      val target = minSpanTreeW()
      val critical = mutableListOf<Int>()
      val pseudo = mutableListOf<Int>()
      edges.indices.forEach {
        if (minSpanTreeW(excluded = it)  > target) critical += it
        else if (minSpanTreeW(included = it) == target) pseudo += it
      }
      return listOf(critical, pseudo)
    }