Introduction

In this blog post, we will explore how to solve the LeetCode problem "1489" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight. Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all. Note that you can return the indices of the edges in any order. Example 1: Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]] Output: [[0,1],[2,3,4,5]] Explanation: The figure above describes the graph. The following figure shows all the possible MSTs: Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output. The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output. Example 2: Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]] Output: [[],[0,1,2,3]] Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical. Constraints: 2 <= n <= 100 1 <= edges.length <= min(200, n * (n - 1) / 2) edges[i].length == 3 0 <= ai < bi < n 1 <= weighti <= 1000 All pairs (ai, bi) are distinct.

Explanation

Here's a breakdown of the solution approach, complexity analysis, and the Python code:

• Key Idea: The core idea is to use Kruskal's algorithm to find the Minimum Spanning Tree (MST) weight. Then, for each edge, we check if it's critical or pseudo-critical by either forcing it into the MST or excluding it and recalculating the MST weight.
• Critical Edge Check: An edge is critical if excluding it increases the MST weight.

• Pseudo-Critical Edge Check: An edge is pseudo-critical if including it results in an MST with the same weight as the original MST.

• Time Complexity: O(m² α(n)), where m is the number of edges, n is the number of vertices, and α(n) is the inverse Ackermann function (which grows very slowly, essentially constant for practical inputs). The m² factor arises from iterating through each edge and then potentially running Kruskal's algorithm (which is O(m α(n))) for each edge. Space Complexity: O(n), primarily for the DSU (Disjoint Set Union) data structure.

Code

    class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            elif self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
            return True  # Indicate that a union occurred
        return False

class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: list[list[int]]) -> list[list[int]]:
        m = len(edges)
        for i in range(m):
            edges[i].append(i)  # Store the original index

        edges.sort(key=lambda x: x[2])  # Sort by weight

        def calculate_mst_weight(include_edge=-1, exclude_edge=-1):
            mst_weight = 0
            num_edges = 0
            dsu = DSU(n)

            if include_edge != -1:
                u, v, weight, index = edges[include_edge]
                if dsu.union(u, v):
                    mst_weight += weight
                    num_edges += 1

            for i in range(m):
                if i == exclude_edge:
                    continue
                u, v, weight, index = edges[i]
                if dsu.union(u, v):
                    mst_weight += weight
                    num_edges += 1

            if num_edges != n - 1:  # Not a valid MST
                return float('inf')
            return mst_weight

        # Calculate the weight of the original MST
        original_mst_weight = calculate_mst_weight()

        critical_edges = []
        pseudo_critical_edges = []

        for i in range(m):
            # Check for critical edges
            weight_without_edge = calculate_mst_weight(exclude_edge=i)
            if weight_without_edge > original_mst_weight:
                critical_edges.append(edges[i][3])  # Append original index
            else:
                # Check for pseudo-critical edges
                weight_with_edge = calculate_mst_weight(include_edge=i)
                if weight_with_edge == original_mst_weight:
                    pseudo_critical_edges.append(edges[i][3])  # Append original index

        return [critical_edges, pseudo_critical_edges]