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

1/**
2 * [1489] Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
3 *
4 * 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.
5 * 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.
6 * Note that you can return the indices of the edges in any order.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2020/06/04/ex1.png" style="width: 259px; height: 262px;" />
10 * 
11 * 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]]
12 * Output: [[0,1],[2,3,4,5]]
13 * Explanation: The figure above describes the graph.
14 * The following figure shows all the possible MSTs:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2020/06/04/msts.png" style="width: 540px; height: 553px;" />
16 * 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.
17 * 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.
18 * 
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2020/06/04/ex2.png" style="width: 247px; height: 253px;" />
21 * 
22 * Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
23 * Output: [[],[0,1,2,3]]
24 * 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.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	2 <= n <= 100
30 * 	1 <= edges.length <= min(200, n * (n - 1) / 2)
31 * 	edges[i].length == 3
32 * 	0 <= ai < bi < n
33 * 	1 <= weighti <= 1000
34 * 	All pairs (ai, bi) are distinct.
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/
40// discuss: https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn find_critical_and_pseudo_critical_edges(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
46        vec![]
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_1489() {
58    }
59}
60