Birliği-bulmak Bu ben cevap çalışıyorum bir görüşme sorudur

Question

sosyal bir ağ olarak ifade:

N üyeleri içeren bir sosyal ağ ve üyelerinin süreleri çiftleri meydana geldiği M damgaları içeren bir günlük dosyası Verilen Arkadaşlıklar, tüm üyelerin bağlı olduğu en erken zamanı belirlemek için bir algoritma tasarlar (yani, her üye bir arkadaşın arkadaşının arkadaşıdır). Günlük dosyasının zaman damgasıyla sıralandığını ve arkadaşlığın eşdeğer bir ilişki olduğunu varsayalım. Algoritmanızın çalışma süresi M log N ya da daha iyisi olmalı ve N ile orantılı ekstra alan kullanmalısınız.

Düşündüğüm ilk şey ... "Bunu yapamam!". Ancak bu sosyal ağın nasıl bir veri yapısı olarak ifade edilebileceğini düşündüm. Sendika bulmak, kullanılabilecek bir veri yapısıdır. Şimdi tüm üyeler bağlandığında ne anlama geldiğini anlamalıyım. Her üye birbiriyle arkadaş olunca gerçek veri yapısını ve neye benzediğini nasıl görebilirim?

Sadece görsel olarak veya kavramsal olarak sistemin tam olarak nasıl bağlanacağını anlayana kadar, o olaya karşılık gelen zaman damgasını nasıl bulacağımı anlamaya başlıyorum.

Answer 1

Sendika bulma veri yapısına bir arkadaşlık eklediğinizde, birleştirilen iki grafik bileşeniyle sonuçlanıp sonuçlanmadığını belirtebilirsiniz. Bu birleştirme etkinliklerinin N-1'ine kadar kenar eklemeyi sürdürmeniz yeterlidir. Sözde kod formunda

:

G := UnionFind(1..N) 
count := 0 
for timestamp, p1, p2 in friendships { 
    if G.Find(p1) != G.Find(p2) { 
     G.Union(p1, p2) 
     count++ 
     if count == N-1 { 
      return timestamp 
     } 
    } 
} 
return +infinity 

Answer 2

Ben günlük dosyası şuna benzer olacağı varsayımı yaptığımız bu egzersiz çözmek için Tamam: İlk

0 1 2015-08-14 18:00:00 
1 9 2015-08-14 18:01:00 
0 2 2015-08-14 18:02:00 
0 3 2015-08-14 18:04:00 
0 4 2015-08-14 18:06:00 
0 5 2015-08-14 18:08:00 
0 6 2015-08-14 18:10:00 
0 7 2015-08-14 18:12:00 
0 8 2015-08-14 18:14:00 
1 2 2015-08-14 18:16:00 
1 3 2015-08-14 18:18:00 
1 4 2015-08-14 18:20:00 
1 5 2015-08-14 18:22:00 
2 1 2015-08-14 18:24:00 
2 3 2015-08-14 18:26:00 
2 4 2015-08-14 18:28:00 
5 5 2015-08-14 18:30:00 

---

2 sayılar, zaman damgasını takip eden arkadaşlığı oluşturan üyelerdir.

Dışarıya çıkarılması gereken bir diğer önemli nokta da, alıştırmanın, dosyanın sıralandığından bahsetmesidir, bu yüzden onu artan bir sıraya göre sıralamaya karar verdim.

Bu bilgilerle, sınıfta sağlanan WeightedQuickUnionFind veri yapısını kullanabilir ve üyeler üzerinde sendika işlemlerini gerçekleştirirken basit işlemi gerçekleştirebilirsiniz, sendika oluşturduktan sonra yapıda kaç bileşenin bulunduğunu sorabilirsiniz. Tüm üyelerin equivalent relation olduğu anlamına gelir. İşte

yaptım kodudur:

public static void main(String[] args) { 

     int n = StdIn.readInt(); 
     WeightedQuickUnion uf = new WeightedQuickUnion(n); 
     String date, time; 
     //timestamps are sorted ascending 
     while (!StdIn.isEmpty()) { 

      int p = StdIn.readInt(); 
      int q = StdIn.readInt(); 
      date = StdIn.readString(); 
      time = StdIn.readString(); 


      uf.union(p, q); 

      StdOut.println("["+p+","+q+"]"); 

      if(uf.getComponents() == 1){ 
       StdOut.println("All members were connected at: " + date + time); 
       break; 
      } 

     } 

---

performans olacak M lg N Eğer M kez (günlük dosyasındaki satırların tutar) yineleme çünkü ve Birlik işlemleri alır: lg n.

Answer 3

Andres tarafından sağlanan cevap doğru olanıdır. Başka bir yol var. Burada N elemanına orantılı ekstra alan kullanabilirsiniz.Bu nedenle, bir ağaçta ve düğümdeki ağaç işlevini birleştirdikten sonra, ağaçtaki düğüm sayısını, kök ağacın düğümdeki düğüm sayısına eklemeniz için eklemeniz gereken toplam düğüm sayısını koruyabilirsiniz. ikinizde. Yani ekledikten sonra sadece yeni ağaçtaki düğümlerin toplam sayısının N'ye eşit olup olmadığını kontrol etmelisiniz. Eğer bu durumda tüm N üyelerinin birbirlerinin arkadaşları olduğu en erken zaman olacaktır.