Latihan 1: Union-Find (Disjoint Set) — Struktur Data

Latihan 1 dari materi Union-Find (Disjoint Set) di Struktur Data — praktek dengan editor kode interaktif, test case otomatis, dan hint terpandu. Langsung jalan di browser.

Lengkapi class UnionFind untuk n orang bernomor 0 sampai n - 1:

constructor(n): bikin array this.parent di mana tiap orang jadi ketua dirinya sendiri, [0, 1, 2, ..., n - 1].
find(x): naik lewat parent sampai ketemu ketuanya, lalu kembalikan ketua itu.
union(x, y): kalau ketua x dan ketua y beda, pasang salah satu ketua di bawah ketua yang lain.
countComponents(): kembalikan jumlah kelompok, yaitu jumlah orang yang parent-nya dirinya sendiri.

Path compression boleh dipakai, tapi gak harus.

Kode di bawah starter mencetak lima baris, urut: 5, 3, true, false, 2.

Class-nya juga dites dengan urutan union lain, jadi hitung dari array parent, jangan menulis angkanya langsung.

Hint

Tiap kelompok punya satu ketua, yaitu orang yang parent-nya dirinya sendiri. Dua orang sekelompok kalau ketuanya sama, dan jumlah kelompok sama dengan jumlah ketua.
Pakai array this.parent. find naik dengan while selama this.parent[x] !== x. union memakai find untuk kedua orang. countComponents menghitung index i yang this.parent[i] === i.
constructor: this.parent = Array.from({ length: n }, (_, i) => i); find: while (this.parent[x] !== x) x = this.parent[x]; return x; union: const rx = this.find(x), ry = this.find(y); if (rx !== ry) this.parent[ry] = rx;

</> { } .css => #id fn()

Versi baru

HyperSheets

bagian dari BelajarWeb.dev

Membuka gerbang…

Latihan 1: Union-Find (Disjoint Set) — Struktur Data

Hint

Memperbarui Aplikasi