DEV Community

1

クラスカル法 (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)

問題

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay