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

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.Comparator;
4import java.util.List;
5
6class Solution {
7    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
8        // Add an edge index to each edge and store it as a new array in the original 'edges' array
9        for (int i = 0; i < edges.length; ++i) {
10            int[] edgeWithIndex = new int[4];
11            System.arraycopy(edges[i], 0, edgeWithIndex, 0, 3);
12            edgeWithIndex[3] = i;
13            edges[i] = edgeWithIndex;
14        }
15      
16        // Sort the edges by their weights
17        Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
18      
19        // Use Kruskal's algorithm to find the minimum spanning tree (MST) and its weight
20        int totalWeight = 0;
21        UnionFind unionFind = new UnionFind(n);
22        for (int[] edge : edges) {
23            if (unionFind.union(edge[0], edge[1])) {
24                totalWeight += edge[2];
25            }
26        }
27      
28        // Initialize the answer list to hold two lists: one for critical, one for pseudo-critical edges
29        List<List<Integer>> answer = new ArrayList<>();
30        for (int i = 0; i < 2; ++i) {
31            answer.add(new ArrayList<>());
32        }
33      
34        // Check each edge to see if it is critical or pseudo-critical
35        for (int[] edge : edges) {
36            int from = edge[0];
37            int to = edge[1];
38            int weight = edge[2];
39            int index = edge[3];
40          
41            // Check if the edge is critical by trying to form a MST without this edge
42            unionFind = new UnionFind(n);
43            int weightWithoutEdge = 0;
44            for (int[] currentEdge : edges) {
45                if (currentEdge[3] != index && unionFind.union(currentEdge[0], currentEdge[1])) {
46                    weightWithoutEdge += currentEdge[2];
47                }
48            }
49            // If it has more components or the total weight without this edge is greater, it's critical
50            if (unionFind.getN() > 1 || (unionFind.getN() == 1 && weightWithoutEdge > totalWeight)) {
51                answer.get(0).add(index); // Add edge index to critical edges list
52                continue;
53            }
54          
55            // Check if the edge is pseudo-critical by adding it first, then forming the MST
56            unionFind = new UnionFind(n);
57            unionFind.union(from, to);
58            int weightWithEdge = weight;
59            for (int[] currentEdge : edges) {
60                if (currentEdge[3] != index && unionFind.union(currentEdge[0], currentEdge[1])) {
61                    weightWithEdge += currentEdge[2];
62                }
63            }
64            // If adding this edge beforehand does not change the total weight, it's pseudo-critical
65            if (weightWithEdge == totalWeight) {
66                answer.get(1).add(index); // Add edge index to pseudo-critical edges list
67            }
68        }
69        return answer;
70    }
71}
72
73class UnionFind {
74    private int[] parent;
75    private int n;
76
77    public UnionFind(int size) {
78        parent = new int[size];
79        this.n = size;
80        for (int i = 0; i < size; ++i) {
81            parent[i] = i;
82        }
83    }
84
85    public int getN() {
86        return n;
87    }
88
89    public boolean union(int x, int y) {
90        int rootX = find(x);
91        int rootY = find(y);
92        if (rootX == rootY) {
93            return false;
94        }
95        parent[rootX] = rootY;
96        --n; // Decrement the number of components
97        return true;
98    }
99
100    public int find(int x) {
101        if (x != parent[x]) {
102            parent[x] = find(parent[x]); // Path compression
103        }
104        return parent[x];
105    }
106}
107

1#include <vector>
2#include <numeric>
3#include <algorithm>
4using std::vector;
5using std::sort;
6using std::iota;
7
8// Union-find data structure to help safely combine nodes into disjoint sets.
9class UnionFind {
10public:
11    vector<int> parent; // Parent array to hold the representative element for each set.
12    int setCount; // Count of disjoint sets.
13
14    // Constructor initializes UnionFind with n elements.
15    UnionFind(int n)
16        : setCount(n), parent(vector<int>(n)) {
17        iota(parent.begin(), parent.end(), 0); // Fill parent array with 0, 1, ..., n-1.
18    }
19
20    // Attempt to merge the sets containing elements 'a' and 'b'.
21    bool unite(int a, int b) {
22        a = find(a);
23        b = find(b);
24        if (a == b) return false; // 'a' and 'b' are already in the same set.
25        parent[a] = b; // Merge the sets.
26        --setCount;
27        return true;
28    }
29
30    // Find the representative element (parent) of the set containing 'x'.
31    int find(int x) {
32        if (parent[x] != x) parent[x] = find(parent[x]); // Path compression.
33        return parent[x];
34    }
35};
36
37class Solution {
38public:
39    // Main function to find critical and pseudo-critical edges in a graph.
40    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
41        // Add the index of the edge to the end of each edge's vector to keep track of them after sorting.
42        for (int i = 0; i < edges.size(); ++i) edges[i].push_back(i);
43      
44        // Sort edges by weight. If weights are equal, it sorts by the indices added above.
45        sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) { return a[2] < b[2]; });
46
47        int minimumSpanningTreeWeight = 0; // To hold the total weight of the minimum spanning tree.
48        UnionFind uf(n); // Create an instance of UnionFind.
49      
50        // Create the minimum spanning tree and calculate its weight.
51        for (auto& edge : edges) {
52            if (uf.unite(edge[0], edge[1])) minimumSpanningTreeWeight += edge[2];
53        }
54      
55        vector<vector<int>> result(2); // Resultant vector to hold critical and pseudo-critical edges.
56      
57        for (auto& edge : edges) {
58            int from = edge[0], to = edge[1], weight = edge[2], index = edge[3];
59            UnionFind ufWithoutEdge(n);
60            int weightWithoutEdge = 0;
61          
62            // Check if removing the edge increases total weight of MST (making it critical).
63            for (auto& nextEdge : edges) {
64                if (nextEdge[3] != index && ufWithoutEdge.unite(nextEdge[0], nextEdge[1]))
65                    weightWithoutEdge += nextEdge[2];
66            }
67          
68            if (ufWithoutEdge.setCount > 1 || (ufWithoutEdge.setCount == 1 && weightWithoutEdge > minimumSpanningTreeWeight)) {
69                result[0].push_back(index); // Edge is critical.
70                continue;
71            }
72          
73            // Check if including the edge doesn't increase total weight of MST (making it pseudo-critical).
74            UnionFind ufWithEdge(n);
75            ufWithEdge.unite(from, to);
76            int weightWithEdge = weight;
77          
78            for (auto& nextEdge : edges) {
79                if (nextEdge[3] != index && ufWithEdge.unite(nextEdge[0], nextEdge[1]))
80                    weightWithEdge += nextEdge[2];
81            }
82          
83            if (weightWithEdge == minimumSpanningTreeWeight) {
84                result[1].push_back(index); // Edge is pseudo-critical.
85            }
86        }
87      
88        return result;
89    }
90};
91

1// Represents the parent array to hold the representative element for each set.
2let parent: number[];
3
4// Represents the count of disjoint sets.
5let setCount: number;
6
7// Initialize UnionFind with n elements.
8function initializeUnionFind(n: number): void {
9  setCount = n;
10  parent = Array.from({ length: n }, (_, index) => index);
11}
12
13// Attempt to merge the sets containing elements 'a' and 'b'.
14function unite(a: number, b: number): boolean {
15  a = find(a);
16  b = find(b);
17  if (a === b) return false; // 'a' and 'b' are already in the same set.
18  parent[a] = b; // Merge the sets.
19  setCount--;
20  return true;
21}
22
23// Find the representative element (parent) of the set containing 'x'.
24function find(x: number): number {
25  if (parent[x] !== x) parent[x] = find(parent[x]); // Path compression.
26  return parent[x];
27}
28
29// Main function to find critical and pseudo-critical edges in a graph
30function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
31  // Add the index of the edge to the end of each edge's array to keep track of them after sorting.
32  edges.forEach((edge, index) => {
33    edge.push(index);
34  });
35
36  // Sort edges by weight. If weights are equal, it sorts by the added indices.
37  edges.sort((a, b) => a[2] - b[2]);
38
39  // To hold the total weight of the minimum spanning tree (MST).
40  let minimumSpanningTreeWeight = 0;
41
42  // Create an instance of UnionFind.
43  initializeUnionFind(n);
44
45  // Create the minimum spanning tree (MST) and calculate its weight.
46  edges.forEach(edge => {
47    if (unite(edge[0], edge[1])) {
48      minimumSpanningTreeWeight += edge[2];
49    }
50  });
51
52  // Resultant array to hold critical and pseudo-critical edges.
53  const result: number[][] = [[], []];
54
55  edges.forEach(edge => {
56    const [from, to, weight, index] = edge;
57    initializeUnionFind(n); // Reset UnionFind without the current edge.
58    let weightWithoutEdge = 0;
59
60    // Check if removing the edge increases the total weight of the MST (making it critical).
61    edges.forEach(nextEdge => {
62      if (nextEdge[3] !== index && unite(nextEdge[0], nextEdge[1])) {
63        weightWithoutEdge += nextEdge[2];
64      }
65    });
66
67    if (setCount > 1 || (setCount === 1 && weightWithoutEdge > minimumSpanningTreeWeight)) {
68      result[0].push(index); // Edge is critical.
69    } else {
70      // Check if including the edge doesn't increase the total weight of the MST (making it pseudo-critical).
71      initializeUnionFind(n);
72      unite(from, to);
73      let weightWithEdge = weight;
74
75      edges.forEach(nextEdge => {
76        if (nextEdge[3] !== index && unite(nextEdge[0], nextEdge[1])) {
77          weightWithEdge += nextEdge[2];
78        }
79      });
80
81      if (weightWithEdge === minimumSpanningTreeWeight) {
82        result[1].push(index); // Edge is pseudo-critical.
83      }
84    }
85  });
86
87  return result;
88}
89