Sorun intro düzey CS bir ders için belirlenmiş ve yüzeyde, çok basit gibi görünen bir soru ile geldi toparlamaya çalışıyorum:

Onların anne adları, doğum tarihleri ve ölüm tarihleri olan kişilerin bir listesi de verilir. , Hayatlarının bir noktasında, bir baba, bir büyükbaba, büyük-büyükbaba, vb kim olduğunu bulmak istiyoruz. Vasiyetle bir algoritma için etiket her kişi ile bu Bilgi olarak bir tamsayı (0 anlamına gelir kişinin hiç bir çocuk, 1 demek o kişi bir ebeveyn, 2 anlamına gelen kişiydi bir büyükbaba, vb.)

Basitlik için, aile, grafik bir ağaç olan bir DAG olduğunu varsayabiliriz.

İlginç burada zor olan sadece ağaç şeklinde bu bilgileri belirlemek için bakabilirsiniz. Örneğin, 8 büyük-büyük dedesi var, ama hiçbiri ben doğduktan sonra hayatta oldukları için, hayatları boyunca hiçbiri büyük büyük dedesi vardı.

Bu sorun zaman içinde çalıştığı için aklıma gelen en iyi algoritma O(n²n kişi sayısıdır.), Fikir basittir - her kişi bir DFS başlayın, en uzak soyundan gelen bu kişinin ölüm tarihinden önce doğmuş aile ağacı bulma. Ancak, bu sorun için en iyi çözüm değildir eminim. Eğer grafik sadece iki anne ve çocukları n ise, örneğin, o zaman sorun O(n) basit çözülebilir. Umut ediyorum da yener O(n . bazı algoritma ^sup>2O kimin zamanı ) veya(n²) en kötü durum.

GüncellemeBu yapabileceğim en iyi çözüm değil, ama bu kadar çok yorum da söz konusu olduğundan bıraktım.

Bir dizi olay (doğum/ölüm), ebeveyn durumu (torunları, anne, baba, büyükbaba, vb.) ve yaşam durumu (canlı, ölü).

Aşağıdaki alanları ile yapıları: verilerimi saklamak istiyorum

mother
father
generations
is_alive
may_have_living_ancestor

Tarihe göre olayları sıralamak ve sonra da her olay için mantık şu iki dersten birini almak:

Birth:
    Create new person with a mother, father, 0 generations, who is alive and may
        have a living ancestor.
    For each parent:
        If generations increased, then recursively increase generations for
            all living ancestors whose generations increased.  While doing that,
            set the may_have_living_ancestor flag to false for anyone for whom it is
            discovered that they have no living ancestors.  (You only iterate into
            a person's ancestors if you increased their generations, and if they
            still could have living ancestors.)

Death:
    Emit the person's name and generations.
    Set their is_alive flag to false.

En kötü durumda yaşayan herkesin atalarının bir sürü varsa, O(n*n). Ancak genel olarak O(n log(n)) olan sıralama ön adım var ve o zaman toplam zaman en toplumlarda O(n log(n)) olma eğilimindedir anlamına gelir O(n * avg no of living ancestors). (Düzgün, @Alexey Kukanov teşekkürler düzeltme için sıralama prestep hesaba katmadım.)