# Cruscal

May 27th, 2024
424
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.
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);