Bir sosyal ağda iki kişinin aynı arkadaş grubuna ait olup olmadığını sormak istiyorsun. Ya da bir haritada iki şehrin birbirine bağlı olup olmadığını. Ya da bir ağdaki kabloları teker teker eklerken hangi noktaların artık aynı ağa dâhil olduğunu takip etmek istiyorsun.
Bu soruların ortak yanı şudur: Elemanlar ayrık gruplara ayrılmıştır, gruplar zamanla birleşir ve sürekli "bu ikisi aynı grupta mı?" diye sorulur. Bu problemi her seferinde grafı gezerek çözebilirsin, ama bu her sorgu için O(V + E) demektir. Union-Find (ayrık kümeler, disjoint set union) veri yapısı aynı işi neredeyse sabit sürede yapar.
Yapının güzelliği, ne kadar sade olduğudur: Yaklaşık otuz satırlık kodla, karmaşıklığı pratikte sabit olan bir yapı elde edersin. Ama bu sadeliğin arkasında, bilgisayar biliminin en ilginç analiz sonuçlarından biri durur: İki küçük iyileştirme uygulandığında, işlem başına maliyet ters Ackermann fonksiyonu kadar olur — evrendeki atom sayısı mertebesindeki girdilerde bile beşten küçük bir sayı.
Ayrık küme problemi
Yapının sunduğu iki işlem vardır:
Find(x) : x'in ait olduğu kümenin TEMSİLCİSİNİ döndürür
Union(x,y) : x ve y'nin kümelerini birleştirir
Aynı kümede mi? → Find(x) == Find(y)Temel fikir, her kümeyi bir ağaç olarak tutmaktır. Her eleman, ebeveynini gösterir; kökün ebeveyni kendisidir ve o, kümenin temsilcisidir.
Başlangıç: her eleman kendi kümesinde
0 1 2 3 4 5
↺ ↺ ↺ ↺ ↺ ↺ (herkes kendi kökü)
Union(0,1), Union(2,3), Union(1,2):
0 4 5
╱ ╲ ↺ ↺
1 2
│
3
Find(3) = 0, Find(1) = 0 → 3 ile 1 aynı kümede
Find(4) = 4 → 4 ayrı kümedeAşağıdaki görselleştirmede birleştirme işlemlerini uygulayarak ağaçların nasıl birleştiğini ve yolların nasıl kısaldığını izleyebilirsin:
Naif uygulama ve sorunu
En basit hâliyle Find, kökü bulana kadar yukarı tırmanır; Union bir kökü diğerine bağlar.
package main
import "fmt"
type NaiveUF struct {
parent []int
steps int // Find sırasında atılan toplam adım
}
func NewNaiveUF(n int) *NaiveUF {
uf := &NaiveUF{parent: make([]int, n)}
for i := range uf.parent {
uf.parent[i] = i // herkes kendi kökü
}
return uf
}
// Find: kökü bulana kadar tırmanır — O(ağaç yüksekliği)
func (u *NaiveUF) Find(x int) int {
for u.parent[x] != x {
x = u.parent[x]
u.steps++
}
return x
}
// Union: bir kökü diğerine bağlar — hiçbir optimizasyon yok
func (u *NaiveUF) Union(x, y int) bool {
rx, ry := u.Find(x), u.Find(y)
if rx == ry {
return false // zaten aynı kümede
}
u.parent[ry] = rx
return true
}
func (u *NaiveUF) Connected(x, y int) bool { return u.Find(x) == u.Find(y) }
func main() {
const n = 10
uf := NewNaiveUF(n)
fmt.Println("başlangıçta 0 ve 5 bağlı mı:", uf.Connected(0, 5))
uf.Union(0, 1)
uf.Union(2, 3)
uf.Union(1, 2)
fmt.Println("0-1, 2-3, 1-2 birleştirildi")
fmt.Println("0 ve 3 bağlı mı:", uf.Connected(0, 3))
fmt.Println("0 ve 5 bağlı mı:", uf.Connected(0, 5))
fmt.Println("zaten bağlı olanları birleştirme:", uf.Union(0, 3))
// EN KÖTÜ DURUM: zincir oluşturan birleştirme sırası
chain := NewNaiveUF(1000)
for i := 0; i < 999; i++ {
chain.Union(i+1, i) // her seferinde yeni kök eskisine bağlanır
}
chain.steps = 0
for i := range 1000 {
chain.Find(i)
}
fmt.Println()
fmt.Println("zincir hâlinde 1000 eleman:")
fmt.Println(" 1000 Find çağrısı için toplam adım:", chain.steps)
fmt.Println(" çağrı başına ortalama:", chain.steps/1000)
fmt.Println(" → ağaç bağlı listeye dönüştü: O(n)")
}başlangıçta 0 ve 5 bağlı mı: false 0-1, 2-3, 1-2 birleştirildi 0 ve 3 bağlı mı: true 0 ve 5 bağlı mı: false zaten bağlı olanları birleştirme: false zincir hâlinde 1000 eleman: 1000 Find çağrısı için toplam adım: 499500 çağrı başına ortalama: 499 → ağaç bağlı listeye dönüştü: O(n)
Sorun net: Hiçbir kural olmadan birleştirirsen ağaç dejenere olabilir ve Find O(n)'e çıkar. Bu, ikili arama ağaçlarındaki dengesizlik probleminin bir başka yüzüdür. Çözüm de benzerdir: ağacı sığ tutmak.
İyileştirme 1: boyuta göre birleştirme
Fikir çok basit: İki ağacı birleştirirken küçük olanı büyüğün altına as. Böylece derinlik gereksiz yere artmaz.
Kötü: büyük ağacı küçüğün altına asmak
1 3
│ → │
2 1
│ │
3 2 ← derinlik arttı
│
4
İyi: küçüğü büyüğün altına asmak
1 1
╱ ╲ → ╱│╲
2 3 2 3 4 ← derinlik aynı kaldıBoyut yerine rank (yüksekliğin üst sınırı) kullanan bir varyant da vardır; ikisi de aynı garantiyi verir. Bu tek iyileştirme bile ağaç yüksekliğini O(log n) ile sınırlar.
İyileştirme 2: yol sıkıştırma
İkinci fikir daha da zariftir: Find çağrıldığında zaten kökü buluyorsun — o hâlde yol üzerindeki tüm düğümleri doğrudan köke bağla. Bir sonraki çağrıda hepsi tek adımda cevap verir.
Find(4) çağrısı öncesi: Find(4) sonrası:
1 1
│ ╱ │ ╲
2 2 3 4
│
3 yol üzerindeki herkes
│ doğrudan köke bağlandı
4Bu, "yaparken düzelt" (self-adjusting) fikrinin güzel bir örneğidir: Yapı, kullanıldıkça kendini iyileştirir.
package main
import "fmt"
type UnionFind struct {
parent []int
size []int // her kökün altındaki eleman sayısı
count int // ayrık küme sayısı
steps int
}
func New(n int) *UnionFind {
uf := &UnionFind{
parent: make([]int, n),
size: make([]int, n),
count: n,
}
for i := range uf.parent {
uf.parent[i] = i
uf.size[i] = 1
}
return uf
}
// Find: yol sıkıştırmalı — neredeyse O(1)
func (u *UnionFind) Find(x int) int {
root := x
for u.parent[root] != root {
root = u.parent[root]
u.steps++
}
// Yol sıkıştırma: yol üzerindeki herkesi doğrudan köke bağla
for u.parent[x] != root {
next := u.parent[x]
u.parent[x] = root
x = next
}
return root
}
// Union: boyuta göre birleştirir
func (u *UnionFind) Union(x, y int) bool {
rx, ry := u.Find(x), u.Find(y)
if rx == ry {
return false
}
if u.size[rx] < u.size[ry] { // küçüğü büyüğün altına as
rx, ry = ry, rx
}
u.parent[ry] = rx
u.size[rx] += u.size[ry]
u.count--
return true
}
func (u *UnionFind) Connected(x, y int) bool { return u.Find(x) == u.Find(y) }
func (u *UnionFind) Count() int { return u.count }
func (u *UnionFind) SetSize(x int) int { return u.size[u.Find(x)] }
func main() {
uf := New(10)
fmt.Println("başlangıç küme sayısı:", uf.Count())
pairs := [][2]int{{0, 1}, {2, 3}, {1, 2}, {5, 6}, {7, 8}, {8, 9}}
for _, p := range pairs {
uf.Union(p[0], p[1])
}
fmt.Println("birleştirmelerden sonra küme sayısı:", uf.Count())
fmt.Println("0 ve 3 bağlı mı:", uf.Connected(0, 3))
fmt.Println("0 ve 5 bağlı mı:", uf.Connected(0, 5))
fmt.Println("0'ın kümesinin boyutu:", uf.SetSize(0))
fmt.Println("7'nin kümesinin boyutu:", uf.SetSize(7))
fmt.Println("4 yalnız mı:", uf.SetSize(4) == 1)
// Aynı zincir senaryosu: artık sorun değil
chain := New(1000)
for i := 0; i < 999; i++ {
chain.Union(i+1, i)
}
chain.steps = 0
for i := range 1000 {
chain.Find(i)
}
fmt.Println()
fmt.Println("zincir hâlinde 1000 eleman (iyileştirmelerle):")
fmt.Println(" 1000 Find çağrısı için toplam adım:", chain.steps)
fmt.Printf(" çağrı başına ortalama: %.2f\n", float64(chain.steps)/1000)
fmt.Println(" → naif sürümde bu sayı 500'ün üzerindeydi")
}başlangıç küme sayısı: 10 birleştirmelerden sonra küme sayısı: 4 0 ve 3 bağlı mı: true 0 ve 5 bağlı mı: false 0'ın kümesinin boyutu: 4 7'nin kümesinin boyutu: 3 4 yalnız mı: true zincir hâlinde 1000 eleman (iyileştirmelerle): 1000 Find çağrısı için toplam adım: 999 çağrı başına ortalama: 1.00 → naif sürümde bu sayı 500'ün üzerindeydi
Ters Ackermann: neden pratikte sabit?
Buradaki α(n), ters Ackermann fonksiyonudur. Ackermann fonksiyonu inanılmaz hızlı büyüyen bir fonksiyondur; tersi de aynı ölçüde yavaş büyür.
α(n) değerleri:
n = 5 → α = 2
n = 2.047 → α = 3
n = 10^19.728 → α = 4
n = evrendeki atom sayısı → α = 4
Yani pratikte α(n) ≤ 4. Sabit sayılabilir.Bu sonuç, iki iyileştirmenin birlikte kullanılmasıyla elde edilir. Yalnızca yol sıkıştırma veya yalnızca boyuta göre birleştirme kullanılırsa karmaşıklık O(log n) olur — hâlâ iyi ama teorik olarak daha zayıf. İkisi birlikte kullanıldığında elde edilen bu sınır, 1975'te Robert Tarjan tarafından kanıtlanmıştır ve algoritma analizi tarihinin en ünlü sonuçlarından biridir.
Pratik sonuç şudur: Union-Find işlemlerini sabit süreli kabul edebilirsin. Milyonlarca elemanlı bir yapıda bile Find çağrısı birkaç bellek erişiminden ibarettir.
Uygulama: bağlı bileşen sayma
Union-Find'in en doğrudan kullanımı budur. Bir grafın kaç ayrı parçadan oluştuğunu bulmak için tüm kenarları gezip birleştirmen yeterlidir.
package main
import (
"fmt"
"maps"
"slices"
)
type UnionFind struct {
parent map[string]string
size map[string]int
count int
}
func New() *UnionFind {
return &UnionFind{parent: map[string]string{}, size: map[string]int{}}
}
func (u *UnionFind) Add(x string) {
if _, ok := u.parent[x]; ok {
return
}
u.parent[x] = x
u.size[x] = 1
u.count++
}
func (u *UnionFind) Find(x string) string {
root := x
for u.parent[root] != root {
root = u.parent[root]
}
for u.parent[x] != root { // yol sıkıştırma
next := u.parent[x]
u.parent[x] = root
x = next
}
return root
}
func (u *UnionFind) Union(x, y string) bool {
u.Add(x)
u.Add(y)
rx, ry := u.Find(x), u.Find(y)
if rx == ry {
return false
}
if u.size[rx] < u.size[ry] {
rx, ry = ry, rx
}
u.parent[ry] = rx
u.size[rx] += u.size[ry]
u.count--
return true
}
func (u *UnionFind) Count() int { return u.count }
// Groups: her kümeyi sıralı biçimde döndürür
func (u *UnionFind) Groups() [][]string {
byRoot := map[string][]string{}
for node := range u.parent {
root := u.Find(node)
byRoot[root] = append(byRoot[root], node)
}
var out [][]string
for _, root := range slices.Sorted(maps.Keys(byRoot)) {
group := byRoot[root]
slices.Sort(group)
out = append(out, group)
}
slices.SortFunc(out, func(a, b []string) int { return len(b) - len(a) })
return out
}
func main() {
uf := New()
// Sosyal ağ: arkadaşlık bağlantıları
friendships := [][2]string{
{"Ayşe", "Mehmet"},
{"Mehmet", "Can"},
{"Zeynep", "Deniz"},
{"Elif", "Burak"},
{"Burak", "Zeynep"},
}
for _, f := range friendships {
uf.Union(f[0], f[1])
}
uf.Add("Kerem") // kimseyle bağlantısı yok
fmt.Println("arkadaş grubu sayısı:", uf.Count())
fmt.Println()
for i, group := range uf.Groups() {
fmt.Printf("grup %d (%d kişi): %v\n", i+1, len(group), group)
}
fmt.Println()
fmt.Println("Ayşe ve Can aynı grupta mı:", uf.Find("Ayşe") == uf.Find("Can"))
fmt.Println("Ayşe ve Zeynep aynı grupta mı:", uf.Find("Ayşe") == uf.Find("Zeynep"))
fmt.Println("Kerem yalnız mı:", uf.size[uf.Find("Kerem")] == 1)
// Yeni bir bağlantı iki grubu birleştirir
fmt.Println()
fmt.Println("Can ile Zeynep arkadaş oldu:", uf.Union("Can", "Zeynep"))
fmt.Println("yeni grup sayısı:", uf.Count())
fmt.Println("Ayşe ve Elif artık aynı grupta mı:", uf.Find("Ayşe") == uf.Find("Elif"))
}arkadaş grubu sayısı: 3 grup 1 (4 kişi): [Burak Deniz Elif Zeynep] grup 2 (3 kişi): [Ayşe Can Mehmet] grup 3 (1 kişi): [Kerem] Ayşe ve Can aynı grupta mı: true Ayşe ve Zeynep aynı grupta mı: false Kerem yalnız mı: true Can ile Zeynep arkadaş oldu: true yeni grup sayısı: 2 Ayşe ve Elif artık aynı grupta mı: true
Bu problemi gezinme algoritmalarıyla da çözebilirsin ve graf sabitse gezinme genelde daha hızlıdır. Union-Find'in üstünlüğü artımlı senaryolarda ortaya çıkar: Kenarlar zamanla eklendikçe bileşen sayısını takip etmen gerekiyorsa, her eklemede grafı baştan gezmek yerine tek bir birleştirme yaparsın.
Uygulama: döngü tespiti
Yönsüz bir grafta döngü olup olmadığını bulmak, Union-Find ile son derece doğaldır: Bir kenarın iki ucu zaten aynı kümedeyse, o kenar bir döngü kapatıyor demektir.
package main
import "fmt"
type UnionFind struct {
parent, size []int
}
func New(n int) *UnionFind {
uf := &UnionFind{parent: make([]int, n), size: make([]int, n)}
for i := range uf.parent {
uf.parent[i] = i
uf.size[i] = 1
}
return uf
}
func (u *UnionFind) Find(x int) int {
root := x
for u.parent[root] != root {
root = u.parent[root]
}
for u.parent[x] != root {
next := u.parent[x]
u.parent[x] = root
x = next
}
return root
}
func (u *UnionFind) Union(x, y int) bool {
rx, ry := u.Find(x), u.Find(y)
if rx == ry {
return false
}
if u.size[rx] < u.size[ry] {
rx, ry = ry, rx
}
u.parent[ry] = rx
u.size[rx] += u.size[ry]
return true
}
type edge struct{ a, b int }
// hasCycle: yönsüz grafta döngü var mı — O(E α(V))
func hasCycle(n int, edges []edge) (bool, edge) {
uf := New(n)
for _, e := range edges {
if !uf.Union(e.a, e.b) {
return true, e // iki uç zaten aynı kümede: döngü
}
}
return false, edge{}
}
// spanningEdges: döngü oluşturmayan kenarları seçer (kapsayan orman)
func spanningEdges(n int, edges []edge) []edge {
uf := New(n)
var kept []edge
for _, e := range edges {
if uf.Union(e.a, e.b) {
kept = append(kept, e)
}
}
return kept
}
func main() {
// Ağaç: döngüsüz
tree := []edge{{0, 1}, {1, 2}, {1, 3}, {3, 4}}
found, e := hasCycle(5, tree)
fmt.Println("ağaç — döngü var mı:", found)
fmt.Println("kenar sayısı:", len(tree), "| düğüm sayısı: 5 | n-1 kuralı:", len(tree) == 4)
// Döngülü graf
cyclic := []edge{{0, 1}, {1, 2}, {2, 3}, {3, 0}, {3, 4}}
found, e = hasCycle(5, cyclic)
fmt.Println()
fmt.Println("döngülü graf — döngü var mı:", found)
if found {
fmt.Printf("döngüyü kapatan kenar: %d-%d\n", e.a, e.b)
}
kept := spanningEdges(5, cyclic)
fmt.Println("kapsayan orman kenarları:", kept)
fmt.Println("atılan kenar sayısı:", len(cyclic)-len(kept))
// Birden çok bileşen ve birden çok döngü
fmt.Println()
messy := []edge{{0, 1}, {1, 0}, {2, 3}, {3, 4}, {4, 2}, {5, 6}}
found, e = hasCycle(7, messy)
fmt.Println("karışık graf — döngü var mı:", found, "| ilk döngü kenarı:", e)
fmt.Println("kapsayan orman:", spanningEdges(7, messy))
}ağaç — döngü var mı: false
kenar sayısı: 4 | düğüm sayısı: 5 | n-1 kuralı: true
döngülü graf — döngü var mı: true
döngüyü kapatan kenar: 3-0
kapsayan orman kenarları: [{0 1} {1 2} {2 3} {3 4}]
atılan kenar sayısı: 1
karışık graf — döngü var mı: true | ilk döngü kenarı: {1 0}
kapsayan orman: [{0 1} {2 3} {3 4} {5 6}]İlk örnekte {1, 0} kenarının döngü sayıldığına dikkat et: Yönsüz grafta {0,1} zaten eklenmişse aynı kenarı tekrar eklemek de bir döngüdür (uzunluğu 2 olan bir döngü). Modelinde çoklu kenara izin veriyorsan bu durumu ayrıca ele alman gerekir.
spanningEdges fonksiyonu, aslında Kruskal algoritmasının iskeletidir. Kenarları ağırlığa göre sıralayıp aynı döngüsüzlük kontrolünü uygularsan minimum kapsayan ağacı elde edersin; bunu Minimum Kapsayan Ağaç dersinde göreceksin.
Union-Find'i ne zaman kullanmalı?
Bu yapı dar ama çok değerli bir problem ailesine hizmet eder. Uygun olduğu durumları tanımak, onu doğru yerde kullanmanı sağlar.
Bağlantılar zamanla ekleniyorsa. Union-Find'in en güçlü olduğu senaryo budur. Kenarlar teker teker gelirken bileşenleri takip etmek, her seferinde grafı yeniden gezmekten kat kat ucuzdur. Ağ kurulumu, kademeli birleşmeler ve akış hâlindeki veri bu desene uyar.
Yalnızca "aynı grupta mı" soruluyorsa. Yapı, iki eleman arasındaki yolu bilmez; yalnızca aynı kümede olup olmadıklarını söyler. Soru buysa, cevabı en ucuza veren yapıdır. Yolun kendisi gerekiyorsa gezinme algoritmalarına ihtiyacın vardır.
Döngü tespiti ve kapsayan ağaç. Yönsüz graflarda döngü bulmak ve minimum kapsayan ağaç kurmak, bu yapının doğrudan uygulamalarıdır.
Eşdeğerlik sınıfları. Denklik ilişkisi tanımlayan her problem — aynı hesaba ait işlemler, aynı nesneyi ifade eden kayıtlar, birleştirilecek yinelenen kullanıcılar — ayrık küme problemidir.
Kümeler yalnızca birleşiyorsa. Bu, yapının en önemli kısıtıdır: Ayırma işlemi yoktur. Bir birleştirmeyi geri almak, standart Union-Find ile mümkün değildir. Ayırma da gerekiyorsa ya işlemleri tersten ele alacak şekilde problemi yeniden düzenlersin ya da geri alınabilir varyantlar kullanman gerekir — ki bunlar yol sıkıştırmadan vazgeçtiği için daha yavaştır.
Son bir not: Union-Find, uygulaması en kolay ileri veri yapılarından biridir. Otuz satırlık bir kod, pek çok problemi çarpıcı biçimde sadeleştirir. Bu oran — az kod, çok kazanç — onu algoritma dünyasının en sevilen araçlarından biri yapar.
Varyantlar ve genişletmeler
Temel yapı çok sadedir ama üzerine eklenebilecek birkaç yaygın genişletme vardır. Bunları bilmek, karşılaştığın problemi doğrudan çözecek varyantı seçmeni sağlar.
Küme boyutu ve istatistik. Her kökte, altındaki eleman sayısını tutmak neredeyse bedavadır ve pek çok problemde doğrudan cevabı verir: en büyük grup, ortalama grup boyutu, tek başına kalan eleman sayısı. Aynı yerde başka özetler de tutulabilir — toplam, en büyük değer, sayaçlar. Tek kural, bu bilginin birleştirme sırasında doğru biçimde güncellenmesidir.
Ağırlıklı ilişkiler. Bazı problemlerde yalnızca "aynı kümede mi" değil, "aralarındaki fark ne" sorusunun da yanıtlanması gerekir. Örneğin bazı değişkenler arasındaki oran ilişkileri verilmişse, bunların tutarlı olup olmadığı ve bilinmeyen oranların hesaplanabilirliği bu yapıyla test edilir. Bunun için her düğümde, ebeveynine göre göreli bir değer saklanır ve yol sıkıştırma sırasında bu değerler birleştirilir.
İki parçalılık ve çelişki tespiti. Kümeleri ikiye ayıran ilişkiler — "bu ikisi aynı grupta olamaz" gibi — eleman sayısını iki katına çıkararak modellenebilir: Her eleman için bir de "karşıtı" tutulur. Bir kısıt eklendiğinde çelişki oluşuyorsa, bu yöntemle anında fark edilir.
Geri alınabilir varyantlar. Yol sıkıştırmadan vazgeçip yalnızca rank ile birleştirme kullanırsan, yapılan değişiklikleri bir yığında tutup geri alabilirsin. Karmaşıklık O(log n)'e çıkar ama bazı algoritmalar — özellikle böl ve fethet yaklaşımıyla zaman içinde geriye giden çözümler — bu yeteneği gerektirir.
Çevrimdışı sorgular. Sorguların tamamı önceden biliniyorsa, bazı problemler işlemleri tersten işleyerek çözülebilir. Silme işlemlerini tersten ele almak, onları birleştirmeye dönüştürür; böylece desteklenmeyen bir işlem, desteklenen bir işleme çevrilmiş olur.
Bu varyantların ortak dersi şudur: Union-Find'in çekirdeği o kadar küçüktür ki, üzerine problem-özel bilgi eklemek genelde birkaç satır alır. Yapıyı ezberlemek yerine fikrini anlamak, bu esnekliği kullanabilmeni sağlar.
Sık yapılan hatalar
- Yalnızca bir iyileştirmeyi uygulamak. Ters Ackermann garantisi, yol sıkıştırma ile boyut/rank birleştirmenin birlikte kullanılmasıyla elde edilir.
Findyerineparentdizisini doğrudan karşılaştırmak.parent[x] == parent[y]yanlış sonuç verir; kökleri karşılaştırmalısın.UnioniçindeFindçağırmayı unutmak. Elemanları değil, köklerini birleştirmelisin.- Ayırma (split) işlemi beklemek. Standart yapıda birleştirme geri alınamaz.
- Küme boyutunu yanlış düğümden okumak. Boyut yalnızca kökte günceldir;
size[Find(x)]yazmalısın. - Yol sıkıştırmayı özyinelemeli yazıp derin ağaçlarda yığın taşırmak. İteratif iki geçişli sürüm daha güvenlidir.
- Yönlü graflarda döngü tespiti için kullanmak. Union-Find yönsüz graflar içindir; yönlü graflarda DFS veya topolojik sıralama gerekir.
Alıştırmalar
Aynı kişiye ait olduğu tespit edilen kullanıcı hesaplarını birleştiren bir sistem yaz. Birleştirme çiftleri verildiğinde kaç benzersiz kişi kaldığını ve her kişinin hangi hesaplara sahip olduğunu raporla.
İpucu
Her hesap bir eleman, her "aynı kişi" bilgisi bir birleştirmedir. Grupları toplarken kökleri anahtar olarak kullan.
Çözümü göster
package main
import (
"fmt"
"maps"
"slices"
)
type UnionFind struct {
parent map[string]string
size map[string]int
}
func New() *UnionFind {
return &UnionFind{parent: map[string]string{}, size: map[string]int{}}
}
func (u *UnionFind) Add(x string) {
if _, ok := u.parent[x]; !ok {
u.parent[x] = x
u.size[x] = 1
}
}
func (u *UnionFind) Find(x string) string {
root := x
for u.parent[root] != root {
root = u.parent[root]
}
for u.parent[x] != root {
next := u.parent[x]
u.parent[x] = root
x = next
}
return root
}
func (u *UnionFind) Union(x, y string) bool {
u.Add(x)
u.Add(y)
rx, ry := u.Find(x), u.Find(y)
if rx == ry {
return false
}
if u.size[rx] < u.size[ry] {
rx, ry = ry, rx
}
u.parent[ry] = rx
u.size[rx] += u.size[ry]
return true
}
func main() {
uf := New()
accounts := []string{
"[email protected]", "[email protected]", "[email protected]",
"[email protected]", "[email protected]",
"[email protected]",
}
for _, a := range accounts {
uf.Add(a)
}
sameUser := [][2]string{
{"[email protected]", "[email protected]"},
{"[email protected]", "[email protected]"},
{"[email protected]", "[email protected]"},
}
merged := 0
for _, p := range sameUser {
if uf.Union(p[0], p[1]) {
merged++
}
}
groups := map[string][]string{}
for _, a := range accounts {
root := uf.Find(a)
groups[root] = append(groups[root], a)
}
fmt.Println("toplam hesap:", len(accounts))
fmt.Println("yapılan birleştirme:", merged)
fmt.Println("benzersiz kişi sayısı:", len(groups))
fmt.Println()
for i, root := range slices.Sorted(maps.Keys(groups)) {
g := groups[root]
slices.Sort(g)
fmt.Printf("kişi %d (%d hesap): %v\n", i+1, len(g), g)
}
fmt.Println()
fmt.Println("iki hesap aynı kişi mi:",
uf.Find("[email protected]") == uf.Find("[email protected]"))
fmt.Println("zaten birleşik olanları birleştirme:",
uf.Union("[email protected]", "[email protected]"))
}toplam hesap: 6 yapılan birleştirme: 3 benzersiz kişi sayısı: 3 kişi 1 (3 hesap): [[email protected] [email protected] [email protected]] kişi 2 (2 hesap): [[email protected] [email protected]] kişi 3 (1 hesap): [[email protected]] iki hesap aynı kişi mi: true zaten birleşik olanları birleştirme: false
Bu, gerçek sistemlerde çok yaygın bir problemdir: Farklı kaynaklardan gelen kayıtların aynı varlığa ait olduğu tespit edildikçe birleştirilmesi. Union-Find, birleştirmeler geldikçe grupları artımlı olarak güncellemeyi çok ucuza getirir.
Bir ızgarada 1'lerin oluşturduğu ada sayısını Union-Find ile bul. Yatay ve dikey komşuluklar bağlantı sayılır; çapraz komşuluk sayılmaz.
İpucu
Her hücreyi satır * sütunSayısı + sütun formülüyle tek bir tamsayıya eşle. Yalnızca sağ ve aşağı komşuları kontrol etmen yeterlidir; sol ve yukarı zaten daha önce işlendi.
Çözümü göster
package main
import "fmt"
type UnionFind struct {
parent, size []int
count int
}
func New(n int) *UnionFind {
uf := &UnionFind{parent: make([]int, n), size: make([]int, n)}
for i := range uf.parent {
uf.parent[i] = i
uf.size[i] = 1
}
return uf
}
func (u *UnionFind) Find(x int) int {
root := x
for u.parent[root] != root {
root = u.parent[root]
}
for u.parent[x] != root {
next := u.parent[x]
u.parent[x] = root
x = next
}
return root
}
func (u *UnionFind) Union(x, y int) bool {
rx, ry := u.Find(x), u.Find(y)
if rx == ry {
return false
}
if u.size[rx] < u.size[ry] {
rx, ry = ry, rx
}
u.parent[ry] = rx
u.size[rx] += u.size[ry]
u.count--
return true
}
func countIslands(grid [][]int) (islands int, largest int) {
if len(grid) == 0 {
return 0, 0
}
rows, cols := len(grid), len(grid[0])
uf := New(rows * cols)
// Kara hücrelerini say
for _, row := range grid {
for _, v := range row {
if v == 1 {
uf.count++
}
}
}
id := func(r, c int) int { return r*cols + c }
for r := range rows {
for c := range cols {
if grid[r][c] != 1 {
continue
}
if c+1 < cols && grid[r][c+1] == 1 { // sağ komşu
uf.Union(id(r, c), id(r, c+1))
}
if r+1 < rows && grid[r+1][c] == 1 { // alt komşu
uf.Union(id(r, c), id(r+1, c))
}
}
}
for r := range rows {
for c := range cols {
if grid[r][c] == 1 {
largest = max(largest, uf.size[uf.Find(id(r, c))])
}
}
}
return uf.count, largest
}
func printGrid(grid [][]int) {
for _, row := range grid {
for _, v := range row {
if v == 1 {
fmt.Print("■ ")
} else {
fmt.Print("· ")
}
}
fmt.Println()
}
}
func main() {
grids := [][][]int{
{
{1, 1, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 1, 0, 1},
{0, 0, 0, 1, 1},
},
{
{1, 0, 1},
{0, 1, 0},
{1, 0, 1},
},
{
{0, 0},
{0, 0},
},
}
for i, grid := range grids {
fmt.Printf("ızgara %d:\n", i+1)
printGrid(grid)
islands, largest := countIslands(grid)
fmt.Println("ada sayısı:", islands, "| en büyük ada:", largest)
fmt.Println()
}
}ızgara 1: ■ ■ · · · ■ ■ · · ■ · · ■ · ■ · · · ■ ■ ada sayısı: 3 | en büyük ada: 4 ızgara 2: ■ · ■ · ■ · ■ · ■ ada sayısı: 5 | en büyük ada: 1 ızgara 3: · · · · ada sayısı: 0 | en büyük ada: 0
İkinci ızgaraya dikkat: Çapraz komşuluk sayılmadığı için beş ayrı ada oluşuyor. Komşuluk tanımını değiştirmek — köşegenleri de dâhil etmek — tamamen farklı bir sonuç üretir; bu yüzden problem tanımında komşuluğun ne anlama geldiği açıkça belirtilmelidir.
Aynı problemi derinlik öncelikli aramayla da çözebilirsin ve kod belki biraz daha kısa olur. Union-Find'i tercih etmek, hücreler dinamik olarak karaya dönüşüyorsa ve her adımda ada sayısını bilmen gerekiyorsa anlamlıdır: O senaryoda gezinme her seferinde baştan yapılmak zorunda kalır.
Şehirleri birbirine bağlayan kablo maliyetleri verilmiş. Tüm şehirlerin birbirine bağlı olmasını sağlayan en ucuz kablo kümesini bul (Kruskal algoritması). Toplam maliyeti, seçilen kabloları ve atlanan kabloları raporla.
İpucu
Kenarları ağırlığa göre sırala, sırayla dene. Bir kenar döngü oluşturmuyorsa (yani Union başarılıysa) seç. n−1 kenar seçince bitir.
Çözümü göster
package main
import (
"fmt"
"slices"
)
type UnionFind struct {
parent, size []int
count int
}
func New(n int) *UnionFind {
uf := &UnionFind{parent: make([]int, n), size: make([]int, n), count: n}
for i := range uf.parent {
uf.parent[i] = i
uf.size[i] = 1
}
return uf
}
func (u *UnionFind) Find(x int) int {
root := x
for u.parent[root] != root {
root = u.parent[root]
}
for u.parent[x] != root {
next := u.parent[x]
u.parent[x] = root
x = next
}
return root
}
func (u *UnionFind) Union(x, y int) bool {
rx, ry := u.Find(x), u.Find(y)
if rx == ry {
return false
}
if u.size[rx] < u.size[ry] {
rx, ry = ry, rx
}
u.parent[ry] = rx
u.size[rx] += u.size[ry]
u.count--
return true
}
type Cable struct {
From, To string
Cost int
}
// kruskal: minimum kapsayan ağacı bulur
func kruskal(cities []string, cables []Cable) (chosen, skipped []Cable, total int, connected bool) {
index := make(map[string]int, len(cities))
for i, c := range cities {
index[c] = i
}
sorted := slices.Clone(cables)
slices.SortFunc(sorted, func(a, b Cable) int {
if a.Cost != b.Cost {
return a.Cost - b.Cost
}
if a.From != b.From {
return cmpStr(a.From, b.From)
}
return cmpStr(a.To, b.To)
})
uf := New(len(cities))
for _, c := range sorted {
if uf.Union(index[c.From], index[c.To]) {
chosen = append(chosen, c)
total += c.Cost
} else {
skipped = append(skipped, c)
}
}
return chosen, skipped, total, uf.count == 1
}
func cmpStr(a, b string) int {
switch {
case a < b:
return -1
case a > b:
return 1
}
return 0
}
func main() {
cities := []string{"Ankara", "İzmir", "Bursa", "Antalya", "Adana"}
cables := []Cable{
{"Ankara", "Bursa", 385},
{"Ankara", "İzmir", 588},
{"Bursa", "İzmir", 330},
{"Ankara", "Adana", 490},
{"İzmir", "Antalya", 445},
{"Antalya", "Adana", 555},
{"Ankara", "Antalya", 540},
}
chosen, skipped, total, connected := kruskal(cities, cables)
fmt.Println("seçilen kablolar (maliyete göre):")
for _, c := range chosen {
fmt.Printf(" %-8s - %-8s %4d km\n", c.From, c.To, c.Cost)
}
fmt.Println()
fmt.Println("atlanan kablolar (döngü oluşturur):")
for _, c := range skipped {
fmt.Printf(" %-8s - %-8s %4d km\n", c.From, c.To, c.Cost)
}
fmt.Println()
fmt.Println("toplam maliyet:", total, "km")
fmt.Println("kablo sayısı:", len(chosen), "| beklenen (n-1):", len(cities)-1)
fmt.Println("tüm şehirler bağlı mı:", connected)
// Kopuk graf senaryosu
fmt.Println()
isolated := append(slices.Clone(cities), "Trabzon")
_, _, total2, connected2 := kruskal(isolated, cables)
fmt.Println("Trabzon eklendi (kablosuz):")
fmt.Println(" toplam maliyet:", total2, "| tüm şehirler bağlı mı:", connected2)
}seçilen kablolar (maliyete göre): Bursa - İzmir 330 km Ankara - Bursa 385 km İzmir - Antalya 445 km Ankara - Adana 490 km atlanan kablolar (döngü oluşturur): Ankara - Antalya 540 km Antalya - Adana 555 km Ankara - İzmir 588 km toplam maliyet: 1650 km kablo sayısı: 4 | beklenen (n-1): 4 tüm şehirler bağlı mı: true Trabzon eklendi (kablosuz): toplam maliyet: 1650 | tüm şehirler bağlı mı: false
Kruskal algoritmasının tamamı bu kadardır: Kenarları sırala, döngü oluşturmayanları seç. Karmaşıklığın baskın terimi sıralamadan gelir; Union-Find işlemleri neredeyse sabit olduğu için toplam maliyete katkısı ihmal edilebilir.
Algoritmanın doğruluğu, "kesme özelliği" (cut property) adı verilen bir teoreme dayanır: Grafı ikiye bölen herhangi bir kesmede en hafif kenar, mutlaka minimum kapsayan ağaçta bulunur. Kenarları artan sırada işlemek bu özelliği her adımda garanti eder.
Son çıktıya dikkat: Bağlantısız bir düğüm eklendiğinde algoritma yine çalışır ama sonuç bir ağaç değil, bir orman olur. Bu durumu tespit etmek için bileşen sayısının 1 olup olmadığını kontrol etmek gerekir. Konunun tamamını Minimum Kapsayan Ağaç dersinde bulabilirsin.
Kısa sınav
Union-Find yapısında Find işlemi ne döndürür?
Yol sıkıştırma (path compression) ne yapar?
Boyuta göre birleştirme neden yapılır?
Her iki iyileştirme birlikte kullanıldığında işlem başına amortize karmaşıklık nedir?
Union-Find hangi işlemi DESTEKLEMEZ?
Yönsüz bir grafta döngü Union-Find ile nasıl tespit edilir?
Özet
- Union-Find, elemanları ayrık kümelerde tutar ve iki işlem sunar:
Find(temsilciyi bul),Union(kümeleri birleştir). - Her küme bir ağaçtır; kök, kümenin temsilcisidir. Aynı kümede olmak, aynı köke sahip olmak demektir.
- Naif uygulamada ağaç dejenere olabilir ve işlemler O(n)'e çıkar.
- Boyuta (veya rank'a) göre birleştirme, küçük ağacı büyüğün altına asarak yüksekliği sınırlar.
- Yol sıkıştırma,
Findsırasında geçilen tüm düğümleri doğrudan köke bağlar. - İki iyileştirme birlikte kullanıldığında amortize maliyet O(α(n))'dir; pratikte 4'ü geçmez, yani sabit sayılır.
- Bağlı bileşen sayma, döngü tespiti ve minimum kapsayan ağaç, en yaygın uygulamalarıdır.
- Yapı yalnızca birleştirmeyi destekler; ayırma işlemi yoktur.
- Kenarlar zamanla eklenirken bileşenleri takip etmek gerektiğinde, gezinme algoritmalarından çok daha verimlidir.