Advertisement
warma2d

Cruscal

May 27th, 2024
424
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const readLine = require('readline');
  2. const reader = readLine.createInterface({input: process.stdin});
  3. const MESSAGE_OOPS = 'Oops! I did it again';
  4.  
  5. let inputLines = [];
  6. let currentLine = 0;
  7. let numberVertices = 0;
  8. let numberEdges = 0;
  9. let source = 0;
  10. let target = 0;
  11. let weight = 0;
  12. let edges = [];
  13.  
  14. reader.on('line', line => inputLines.push(line))
  15. process.stdin.on('end', solve);
  16.  
  17. function solve() {
  18.     for (const line of inputLines) {
  19.         if (currentLine === 0) {
  20.             [numberVertices, numberEdges] = line.split(' ');
  21.             numberVertices = numberVertices*1;
  22.             numberEdges = numberEdges*1;
  23.         } else {
  24.             if (currentLine <= numberVertices) {
  25.                 [source, target, weight] = line.split(' ');
  26.                 edges.push([(source-1), (target-1), weight*1]);
  27.             }
  28.         }
  29.         currentLine++;
  30.     }
  31.  
  32.     console.log(kruskalMaxMst(numberVertices, edges));
  33. }
  34.  
  35. // возвратить идентификатор множества, которому принадлежит элемент
  36. function find(parent, vertex) {
  37.     if (parent[vertex] != vertex) {
  38.         parent[vertex] = find(parent, parent[vertex]);
  39.     }
  40.  
  41.     return Number(parent[vertex]);
  42. }
  43.  
  44. function union(parent, rank, root1, root2) {
  45.     if (Number(rank[root1]) > Number(rank[root2])) {
  46.         parent[root2] = Number(root1);
  47.     } else if (Number(rank[root1]) < Number(rank[root2])) {
  48.         parent[root1] = Number(root2);
  49.     } else {
  50.         parent[root2] = Number(root1);
  51.         rank[root1] += 1;
  52.     }
  53. }
  54.  
  55. function kruskalMaxMst(n, edges) {
  56.     edges.sort((a, b) => b[2] - a[2]); // DESC by weight
  57.     const parent = Array.from({ length: n }, (_, i) => i);
  58.     const rank = new Array(n).fill(0);
  59.  
  60.     let maxMstWeight = 0;
  61.  
  62.     for (const [u, v, weight] of edges) {
  63.         const rootU = find(parent, u);
  64.         const rootV = find(parent, v);
  65.         if (rootU != rootV) {
  66.             union(parent, rank, rootU, rootV);
  67.             maxMstWeight += weight;
  68.         }
  69.     }
  70.  
  71.     let components = new Set();
  72.     for (let i = 0; i < n; i++) {
  73.         let q = find(parent, i);
  74.         components.add(q);
  75.     }
  76.  
  77.     if (components.size >= 2) {
  78.         return MESSAGE_OOPS;
  79.     }
  80.  
  81.     return maxMstWeight;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement