クラスカル法 (Kruskal's Algorithm)

コード

let input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.trim().split("\n")
let v, e, path = []

for (let i = 0; i < lines.length; i++) {
  if (i === 0) {
    [v, e] = lines[i].split(" ")
    continue
  }
  path.push(lines[i].split(" ").map(v => parseInt(v)))
}

const DisjointSet = function () {
  this.m = new Map()
}

DisjointSet.prototype.add = function (val) {
  this.m.set(val, new Node(val))
}

DisjointSet.prototype.union = function (val1, val2) {
  const p1 = this.find(this.m.get(val1).val)
  const p2 = this.find(this.m.get(val2).val)
  if (p1.rank === p2.rank) {
    p2.rank++
    p1.parent = p2
  } else if (p1.rank < p2.rank) {
    p1.parent = p2
  } else {
    p2.parent = p1
  }
}

DisjointSet.prototype.find = function (val) {
  let cur = this.m.get(val)
  if (cur.parent != cur) {
    cur.parent = this.find(cur.parent.val)
  }
  return cur.parent
}

const Node = function (val) {
  this.val = val
  this.parent = this
  this.rank = 1
}

function kruskal(v, path) {
  path.sort((a, b) => a[2] - b[2])

  // initialize nodes
  const ds = new DisjointSet()
  for (let i = 0; i < v; i++) {
    ds.add(i)
  }
  let total = 0
  for (const [s, t, w] of path) {
    if (ds.find(s) === ds.find(t)) {
      continue
    }
    ds.union(s, t)
    total += w
  }
  console.log(total)
}

// console.log(v, e)
// console.log(path)
kruskal(v, path)

問題

• https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_1_