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

Problem Description

You are given an undirected, connected graph with n nodes labeled from 0 to n-1 and an array edges where edges[i] = [from_i, to_i, weight_i] represents an edge between nodes from_i and to_i with a certain weight.

Your task is to find all critical and pseudo-critical edges in any minimum spanning tree (MST) of the graph:

An edge is critical if removing it increases the total weight of the MST or makes it impossible to form an MST (i.e., the edge is in every MST).
An edge is pseudo-critical if it can appear in some MST (i.e., including it in the MST does not increase the total weight), but is not critical.

You must return a list containing two lists:

The first list contains the indices of all critical edges.
The second list contains the indices of all pseudo-critical edges.

Constraints:

1 ≤ n ≤ 100
edges.length == m, 1 ≤ m ≤ min(200, n * (n - 1) / 2)
0 ≤ from_i < to_i < n
1 ≤ weight_i ≤ 1000
All pairs (from_i, to_i) are unique.

Thought Process

The problem is about identifying which edges must appear in every minimum spanning tree (critical), and which edges can appear in some but not all minimum spanning trees (pseudo-critical).

The brute-force way would be to enumerate all possible MSTs and see which edges appear in all or some of them. However, this is computationally infeasible for larger graphs due to the combinatorial explosion.

Instead, we can use properties of Kruskal's algorithm and MSTs:

If removing an edge increases the cost of the MST, that edge is critical.
If forcibly including an edge (even if it's not needed) does not increase the cost of the MST, it is pseudo-critical.

By simulating the MST construction with and without each edge, we can efficiently classify each edge.

Solution Approach

We use Kruskal's algorithm and the Union-Find (Disjoint Set Union) data structure for efficient MST construction and cycle detection.

Annotate Edges: Since the problem requires returning indices, we first annotate each edge with its original index.
Sort Edges: Sort the edges by weight, as Kruskal's algorithm does.
Compute MST Weight: Use Kruskal's algorithm to compute the minimum total weight of the MST for the original graph.
Check Each Edge: For each edge, perform two checks:
- Critical Check: Remove the edge and compute the MST. If the MST weight increases or the MST cannot be formed (graph disconnected), the edge is critical.
- Pseudo-Critical Check: Force-include the edge at the beginning, then run Kruskal's algorithm for the remaining edges. If the MST weight is the same as the original, the edge is pseudo-critical (unless already classified as critical).
Collect Results: Gather indices of critical and pseudo-critical edges as required.

The Union-Find data structure is used to efficiently track connected components and avoid cycles during MST construction.

Example Walkthrough

Example 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]]

Annotate Edges: Each edge is given an index:
edges = [[0,1,1,0],[1,2,1,1],[2,3,2,2],[0,3,2,3],[0,4,3,4],[3,4,3,5],[1,4,6,6]]
Sort Edges: Already sorted by weight.
Compute MST Weight: Using Kruskal's algorithm, the MST includes edges 0, 1, 2, 4 for a total weight of 1+1+2+3=7.
Critical Check for Edge 0: Remove edge 0, recompute MST. The new MST weight is 8 (>7), so edge 0 is critical.
Pseudo-Critical Check for Edge 0: Not needed since it's already critical.
Repeat for all edges: Edge 1 is also critical. Edge 2 is pseudo-critical (including it does not increase the MST weight), etc.
Result: [[0,1],[2,3,4,5]]

Time and Space Complexity

Brute-force: Enumerating all MSTs would be exponential in the number of edges, which is infeasible for large graphs.

Optimized Approach:

For each edge, we run Kruskal's algorithm twice (once for critical check, once for pseudo-critical check).
Kruskal's algorithm runs in O(m log m) time, where m is the number of edges.
For m edges, total time complexity is O(m^2 log m).
Space complexity is O(m + n) due to storing edges and the Union-Find data structure.

Summary

This problem leverages MST properties and Kruskal's algorithm to efficiently classify edges as critical or pseudo-critical. By simulating MST construction with and without each edge, we avoid brute-force enumeration and use the Union-Find structure for cycle detection and component tracking. The approach is systematic, efficient, and highlights the connection between MST algorithms and edge importance in network design.

Code Implementation

class UnionFind:
    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])
        return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return False
        if self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        else:
            self.parent[yr] = xr
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1
        return True

class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n, edges):
        edges = [edge + [i] for i, edge in enumerate(edges)]
        edges.sort(key=lambda x: x[2])

        def kruskal(skip=None, force=None):
            uf = UnionFind(n)
            weight = 0
            count = 0
            if force is not None:
                u, v, w, i = edges[force]
                if uf.union(u, v):
                    weight += w
                    count += 1
            for idx, (u, v, w, i) in enumerate(edges):
                if idx == skip:
                    continue
                if uf.union(u, v):
                    weight += w
                    count += 1
            return weight if count == n-1 else float('inf')

        minWeight = kruskal()
        critical, pseudo = [], []
        for i in range(len(edges)):
            # Check critical
            if kruskal(skip=i) > minWeight:
                critical.append(edges[i][3])
            elif kruskal(force=i) == minWeight:
                pseudo.append(edges[i][3])
        return [critical, pseudo]

class UnionFind {
public:
    vector<int> parent, rank;
    UnionFind(int n): parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int xr = find(x), yr = find(y);
        if (xr == yr) return false;
        if (rank[xr] < rank[yr]) parent[xr] = yr;
        else {
            parent[yr] = xr;
            if (rank[xr] == rank[yr]) rank[xr]++;
        }
        return true;
    }
};

class Solution {
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        int m = edges.size();
        vector<vector<int>> newEdges;
        for (int i = 0; i < m; ++i) {
            auto e = edges[i];
            e.push_back(i);
            newEdges.push_back(e);
        }
        sort(newEdges.begin(), newEdges.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });

        auto kruskal = [&](int skip, int force) {
            UnionFind uf(n);
            int weight = 0, count = 0;
            if (force != -1) {
                auto& e = newEdges[force];
                if (uf.unite(e[0], e[1])) {
                    weight += e[2];
                    count++;
                }
            }
            for (int i = 0; i < m; ++i) {
                if (i == skip) continue;
                auto& e = newEdges[i];
                if (uf.unite(e[0], e[1])) {
                    weight += e[2];
                    count++;
                }
            }
            return count == n-1 ? weight : INT_MAX;
        };

        int minWeight = kruskal(-1, -1);
        vector<int> critical, pseudo;
        for (int i = 0; i < m; ++i) {
            if (kruskal(i, -1) > minWeight)
                critical.push_back(newEdges[i][3]);
            else if (kruskal(-1, i) == minWeight)
                pseudo.push_back(newEdges[i][3]);
        }
        return {critical, pseudo};
    }
};

class UnionFind {
    int[] parent, rank;
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
    public boolean union(int x, int y) {
        int xr = find(x), yr = find(y);
        if (xr == yr) return false;
        if (rank[xr] < rank[yr]) parent[xr] = yr;
        else {
            parent[yr] = xr;
            if (rank[xr] == rank[yr]) rank[xr]++;
        }
        return true;
    }
}

class Solution {
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        int m = edges.length;
        int[][] newEdges = new int[m][4];
        for (int i = 0; i < m; ++i) {
            newEdges[i][0] = edges[i][0];
            newEdges[i][1] = edges[i][1];
            newEdges[i][2] = edges[i][2];
            newEdges[i][3] = i;
        }
        Arrays.sort(newEdges, (a, b) -> Integer.compare(a[2], b[2]));

        int minWeight = kruskal(n, newEdges, -1, -1);
        List<Integer> critical = new ArrayList<>();
        List<Integer> pseudo = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            if (kruskal(n, newEdges, i, -1) > minWeight)
                critical.add(newEdges[i][3]);
            else if (kruskal(n, newEdges, -1, i) == minWeight)
                pseudo.add(newEdges[i][3]);
        }
        List<List<Integer>> res = new ArrayList<>();
        res.add(critical);
        res.add(pseudo);
        return res;
    }

    private int kruskal(int n, int[][] edges, int skip, int force) {
        UnionFind uf = new UnionFind(n);
        int weight = 0, count = 0;
        if (force != -1) {
            int[] e = edges[force];
            if (uf.union(e[0], e[1])) {
                weight += e[2];
                count++;
            }
        }
        for (int i = 0; i < edges.length; ++i) {
            if (i == skip) continue;
            int[] e = edges[i];
            if (uf.union(e[0], e[1])) {
                weight += e[2];
                count++;
            }
        }
        return count == n-1 ? weight : Integer.MAX_VALUE;
    }
}

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x)
            this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x, y) {
        let xr = this.find(x), yr = this.find(y);
        if (xr === yr) return false;
        if (this.rank[xr] < this.rank[yr]) this.parent[xr] = yr;
        else {
            this.parent[yr] = xr;
            if (this.rank[xr] === this.rank[yr]) this.rank[xr]++;
        }
        return true;
    }
}

var findCriticalAndPseudoCriticalEdges = function(n, edges) {
    let newEdges = edges.map((e, i) => [...e, i]);
    newEdges.sort((a, b) => a[2] - b[2]);

    function kruskal(skip, force) {
        let uf = new UnionFind(n);
        let weight = 0, count = 0;
        if (force !== -1) {
            let [u, v, w, idx] = newEdges[force];
            if (uf.union(u, v)) {
                weight += w;
                count++;
            }
        }
        for (let i = 0; i < newEdges.length; ++i) {
            if (i === skip) continue;
            let [u, v, w, idx] = newEdges[i];
            if (uf.union(u, v)) {
                weight += w;
                count++;
            }
        }
        return count === n - 1 ? weight : Infinity;
    }

    let minWeight = kruskal(-1, -1);
    let critical = [], pseudo = [];
    for (let i = 0; i < newEdges.length; ++i) {
        if (kruskal(i, -1) > minWeight)
            critical.push(newEdges[i][3]);
        else if (kruskal(-1, i) === minWeight)
            pseudo.push(newEdges[i][3]);
    }
    return [critical, pseudo];
};

AlgoMap.io

Want Help Cracking FAANG?