"Birlik ve bulmak" ayrık kümeler için vardır. http://en.wikipedia.org/wiki/Union_findBiliyoruz
Ama nasıl ters işlem yapmak ? E kenarlarına bağlı N düğümleri olan bir seti düşünün (aslında bir grafiktir). Ve her adımda, biraz kenar silmek ve bu silme işleminin başka bir ayrık sete sahip olup olmadığını kontrol etmek istiyoruz. "Birlik ve bulmak" gibi hızlı bir şekilde yapmak mümkün mü?
P.S. bu biz tatil :)
Bu çevrimiçi kenar silme sorunu veya çevrimiçi bağlantı sorunu olarak bilinir var, ödev değil. Bazı algoritmalara bağlantılar bu section of the Wikipedia article on graph connectivity'dadır.
Yani soru verimli bir Bridge algılamak nasıl? Bu doğrusal zamanda yapılabilir (ayrıca bağlantıya bakınız).
@Chris görünüşe göre her aşamada tespit köprüler olduğunu daha verimli olabilir (o "her adımda" diyor) art arda operasyon yapmak istediği göz önüne alındığında. – borrible
Bu köprüyü algoritmayı bulup köprüleri işaretlerseniz ve grafiğe bir kenar eklenmedikçe yeni köprülerin görünmeyeceğini; Bu grafikte bulunan tüm köprüler, kenarlar kaldırıldıkça köprüler olarak kalır ve yeni köprüler yalnızca köprü olmayan bir kenarı kaldırırsanız görünebilir; Bu nedenle, sadece iki alt küme üzerindeki algoritmanın yeniden çalıştırılması gerekiyor, yeni kaldırılmış olan köprü dışı bir kenar tarafından bağlanmış. –
Birliği-Bul sürekli bir döngü yapmaz minimum ağırlığı kenar ekler Kruskal algoritması kullanılır. Bir ters fikir - sürece grafik kesmez maksimum ağırlık kenarların alınması - görünüşte bazı karmaşık veri yapısı (Wikipedia bakınız) yararlanabilirler olan reverse-delete algorithm kullanılır.
Sonraki güzel bağlantı, ama çok genelleştirilmiş ve gerçekten görmek için kod yok :( – Spinach
Bağlantı için teşekkürler. ACM'de satın almak için sadece makaleleri bulabilirim. TopCoder herhangi bir bilgi, herhangi bir doğrudan bağlantı bulamadın mı? :) – Spinach