Day 105: find the key edge and pseudo key edge in the minimum spanning tree

Address: leetcode-cn.com/problems/fi…

Kruskal algorithm + and search set. Headache problem, copy the problem.

/** * @param {number} n * @param {number[][]} edges * @return {number[][]} */ var findCriticalAndPseudoCriticalEdges = Function (n, edges) {// edges. Record the initial index number of the edge, and sort it (because the result is returned with the edge indexed) // 2. Firstly, kruskal algorithm is used to calculate the weight and minCosts // 3 of the minimum spanning tree. Find the key edge: After removing an edge, run Kruskal algorithm. If the sum of the weights of its minimum spanning tree is larger than minCosts or disconnected, then this edge is the key edge // 4. Pseudo-critical edge: If an edge is not a critical edge and its weight is still the same as minCosts after it is included in the minimum spanning tree, then it is a pseudo-critical edge // 1. For (let I = 0; i < edges.length; i++) { edges[i].push(i); } edges.sort((a, b) => a[2] - b[2]); MinCosts let minCosts = MST(-1, false); // We use -1 and false to indicate that neither edge is indicated // 3.4. Const ans = [[], []]; for(let k = 0; k < edges.length; k++) { if(MST(k, false) > minCosts) ans[0].push(edges[k][3]); Else if(MST(k, true) === minCosts) ans[1]. Push (edges[k][3]); Function MST(k, hasK) {let cost = 0, count = 0; let cost = 0; const unionFindSet = new UnionFind(n); // If (hasK) {unionFindSet. Union (edges[k][0], edges[k][1]); cost += edges[k][2]; count++; } for(let I = 0; i < edges.length; i++) { if(! hasK && i === k) continue; If I ===k, skip if(! UnionFindSet. Union (edges[I][0], [I][1])) {// Connects two dissimilar fluxes cost += edges[I][2]; count++; if(count === n - 1) break; }} return count === n-1? cost : Infinity; } return ans;} return ans; }; Constructor (n) {this.parents = Array(n).fill(0).map((value, index) => index); constructor(n) {this.parents = Array(n).fill(0).map((value, index) => index); this.ranks = Array(n).fill(0); } find(x) { if(this.parents[x] ! == x) { this.parents[x] = this.find(this.parents[x]); } return this.parents[x]; } union(x, y) { let rootX = this.find(x), rootY = this.find(y); if(rootX === rootY) return true; if(this.ranks[rootX] > this.ranks[rootY]) { this.parents[rootY] = rootX; } else if(this.ranks[rootX] < this.ranks[rootY]) { this.parents[rootX] = rootY; } else { this.parents[rootY] = rootX; this.ranks[rootX]++; } return false; }}Copy the code

Execution time: 208 ms, beating 66.67% of users in all JavaScript commits

Memory consumption: 46.9 MB, beating 33.33% of all JavaScript commits