Number of Provinces
0 ile n-1 arasında numaralandırılmış n şehir vardır. Satır listesi olarak bir n × n matrisi olan isConnected verilir: isConnected[i][j], i şehri ile j şehri arasında doğrudan bir yol varsa 1, yoksa 0 değerini alır. Yollar iki yönde de kullanılabildiğinden matris simetriktir ve her şehir kendisine bağlı sayılır.
Bir eyalet, doğrudan veya başka şehirler üzerinden birbirine ulaşabilen ve gruptan dışarıya giden yolu olmayan şehirlerden oluşan bir gruptur. Eyalet sayısını döndür.
Fonksiyon
- isConnectedinteger-2d-array
- n × n matrisi; iki şehri doğrudan bir yol bağlıyorsa 1
- Döndürürinteger
- il sayısı
Kısıtlar
1 ≤ n ≤ 150; buradan = isConnected.lengthisConnected[i].length = nisConnected[i][j]değeri0veya1'dirisConnected[i][i] = 1isConnected[i][j] = isConnected[j][i]
Örnekler
- Girdi
- isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
- Çıktı
- 2
- Açıklama
- 0 şehrinin 3 şehrine giden bir yolu, 1 şehrinin ise 2 şehrine giden bir yolu vardır. İki çift arasında hiçbir yol olmadığından 2 il vardır.
- Girdi
- isConnected = [[1, 1, 0, 0, 0], [1, 1, 1, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]]
- Çıktı
- 3
- Açıklama
- 0 ve 2 numaralı şehirler arasında yol yoktur, ancak ikisinin de 1 numaralı şehre giden bir yolu vardır; bu nedenle 0, 1 ve 2 numaralı şehirler tek bir il oluşturur. 3 ve 4 numaralı şehirlerin hiç yolu yoktur ve her biri bir il oluşturur; toplamda 3 il vardır.
Gönderirken +15 gizli test
Ek soru
Artık her yol belirli bir günde açılıyor. Tüm şehirlerin tek bir eyalete bağlı olduğu ilk günü bulabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Her şehri bir nokta, köşegen dışındaki her
1değerini de iki nokta arasındaki bir çizgi olarak gösterin. Bu görselde bir il nasıl görünür?Bir il, bağlantılı bir bileşendir: İki şehir arasındaki 0, onların ayrı olduğu anlamına gelmez; çünkü üçüncü bir şehir onları birbirine bağlayabilir. Daha önceki aramaların ulaşmadığı bir şehirden kaç kez yeni bir arama başlatmanız gerektiğini sayın.
Başka bir yol: şehir başına bir grup olacak şekilde
ngrupla başlayın ve köşegenin üstündeki her 1 içinivejgruplarını birleştirin. İki farklı grubun birleştirilmesi sayıyı bir azaltır. Yol sıkıştırmalı bir union-find, her birleştirme işlemini neredeyse sabit zamanda gerçekleştirir.
Çözüm
Matris, yönsüz bir grafiğin komşuluk matrisidir: şehirler düğümlerdir ve i satırında, j sütunundaki 1 bir kenarı ifade eder. Bir il, bağlantılı bir bileşendir; dolayısıyla yanıt bileşenlerin sayısıdır. Tuzak, üçüncü bir şehir üzerinden ulaşılabilmesidir: iki şehir arasındaki 0, onları farklı illere ayırmaz. Ziyaret edilmemiş her şehirden başlatılan bir arama veya her kenarın iki ucunu birleştiren bir union-find, matrisin kendi boyutu olan O(n²) sürede bileşenleri sayar.
Derinlik öncelikli arama: ziyaret edilmemiş her şehirden
Sezgi
Şehirleri sırayla dolaşın. Daha önceki hiçbir aramanın işaretlemediği bir şehirle karşılaştığınızda, bu şehir daha önce saydığınız bir eyalete ait olamaz; çünkü her arama o eyaletin tamamını işaretler. Bu yüzden sayacı bir artırın, ardından bu şehrin ulaşabildiği tüm şehirleri işaretleyin.
Bu şehirleri bulmak için bir yığın kullanın. Bir şehri yığından çıkarın, matrisin o şehre karşılık gelen satırını okuyun ve bu satırda 1 bulunan, henüz işaretlenmemiş her şehri işaretleyerek yığına ekleyin. İkinci örnekte, 0 numaralı şehirden yapılan arama 1 numaralı şehri yığına ekler; ardından 1 numaralı şehrin satırı, 0 numaralı satırda 2 numaralı şehir için 0 olmasına rağmen 2 numaralı şehri ekler. Satırları bu şekilde izlemek, yalnızca başka şehirler üzerinden bağlantılı olan şehirleri bulmanızı sağlar.
Her şehir yığından bir kez çıkarılır ve çıkarılırken n girdiden oluşan satırı okunur; dolayısıyla toplam çalışma süresi O(n²)'dir: matrisi bir kez okursunuz. İşaretler ve yığın en fazla n şehir tutar; bu nedenle ek alan kullanımı O(n)'dir.
Özyinelemeli arama daha derli toplu görünür, ancak tek uzun bir çizgi şeklindeki bir eyalette çağrılar şehir başına bir kez iç içe geçer. n = 150 için bu güvenlidir; aynı kod 10^5 düğümlü bir grafikte çağrı yığınını taşırır. Bu nedenle açık yığın kullanma alışkanlığını sürdürmeye değer.
Algoritma
- Her şehir için bir görülme işareti oluştur ve sayacı 0 olarak ayarla.
- Şehirleri sırayla incele ve daha önce görülmüş şehirleri atla.
- Görülmemiş bir şehirde sayacı 1 artır, şehri işaretle ve bir yığına ekle.
- Yığında şehir olduğu sürece birini çıkar ve satırında 1 olan ve henüz görülmemiş her şehri yığına ekle; eklerken işaretle.
- Sayaç değerini döndür.
def findCircleNum(isConnected):
n = len(isConnected)
seen = [False] * n
provinces = 0
for start in range(n):
if seen[start]:
continue
# Nobody reached this city from an earlier province, so it starts a new one.
provinces += 1
seen[start] = True
stack = [start]
while stack:
city = stack.pop()
row = isConnected[city]
for other in range(n):
# Mark a city when you push it, so it is never pushed twice.
if row[other] == 1 and not seen[other]:
seen[other] = True
stack.append(other)
return provincesYol sıkıştırma ve dereceye göre birleştirme ile birleşim-bulma
Sezgi
Soruyu tersinden düşünün. n il ile başlayın; her şehir bir il olsun. Matristeki her 1, iki şehrin birlikte olduğunu belirtir: Hâlâ farklı gruplardalarsa grupları birleştirin ve sayı bir azalır. Son yolun ardından sayı cevaptır. Matris simetrik olduğu ve köşegen bir şehri kendisine bağladığı için yalnızca köşegenin üstündeki girişlere ihtiyacınız var. İkinci örnekte sayı 5'ten başlar. (0, 1) konumundaki 1, 0 ve 1 şehirlerini birleştirir (geriye 4 kalır); (1, 2) konumundaki 1 ise 1 şehrinin 0 şehrinin grubunda olduğunu görür ve 2 şehrini de gruba katar (geriye 3 kalır). 3 ve 4 şehirlerinin köşegenin üstünde 1'i yoktur, dolayısıyla cevap 3'tür.
Disjoint set union olarak da adlandırılan union-find, her grubu bir ağaç olarak saklar. parent[c] bir adım yukarıyı gösterir; ebeveyni kendisi olan en üstteki şehir, grubun köküdür. İki şehir ancak find ikisini de yukarı doğru aynı köke götürüyorsa aynı gruptadır. İki grubu birleştirmek için köklerden birini diğerini gösterecek şekilde ayarlayın.
İki kural ağaçları dengeli tutar. Ranka göre birleştirme, daha kısa ağacı daha uzun ağacın altına bağlar; böylece yüksekliği h olan bir ağaç en az 2^h şehir içerir ve hiçbir yol log n'den uzun olmaz. Yol sıkıştırma işi daha da ileri götürür: find kökü bulduğunda, geçtiği her şehri doğrudan o köke bağlar; böylece bu şehirlerden herhangi birinden yapılan bir sonraki arama tek adım sürer. Bu kurallardan biri olmadan, uzun bir zincirdeki şehirleri şanssız bir sırayla birleştirmek tek bir yoldan oluşan bir ağaç oluşturur ve her find O(n) adım yürür.
Her iki kuralla birlikte, her find işleminin amortize maliyeti O(α(n)) olur; burada α, bir bilgisayarın tutabileceği herhangi bir n değeri için en fazla 4 olan ters Ackermann fonksiyonudur. Matrisi okumak yine O(n²) maliyetlidir; dolayısıyla toplam süre budur ve parent ile rank dizileri O(n) alan kullanır. Yollar birer birer geldiğinde bu yapı kendini gösterir: yeniden arama yapmadan her yeni yoldan sonra sayıyı güncel tutar.
Algoritma
- Her şehir için
parent[c] = cverank[c] = 0ayarlayın ve sayıyınolarak belirleyin. isConnected[i][j] = 1olan heri < jçifti içinivejşehirlerinin köklerini bulun.findiçinde köke kadar ilerleyin, ardından aynı yolu tekrar izleyin ve üzerindeki her şehri doğrudan köke bağlayın.- Kökler farklıysa, daha düşük dereceli kökü diğerinin altına bağlayın, dereceler eşitse dereceye 1 ekleyin ve sayıdan 1 çıkarın.
- Sayıyı döndürün.
def findCircleNum(isConnected):
n = len(isConnected)
parent = list(range(n))
rank = [0] * n
def find(city):
root = city
while parent[root] != root:
root = parent[root]
# Path compression: point every city on the way straight at the root.
while parent[city] != root:
up = parent[city]
parent[city] = root
city = up
return root
provinces = n
for i in range(n):
for j in range(i + 1, n): # the matrix is symmetric, so the upper half is enough
if isConnected[i][j] == 1:
a, b = find(i), find(j)
if a == b:
continue
# Union by rank: hang the shorter tree under the taller one.
if rank[a] < rank[b]:
a, b = b, a
parent[b] = a
if rank[a] == rank[b]:
rank[a] += 1
# Two provinces just became one.
provinces -= 1
return provinces
Tuzaklar ve uç durumlar
Çoğu yanlış yanıt, 0'ı iki şehrin ayrı olduğunun kanıtı olarak görür ya da bileşenler yerine başka bir şeyi sayar.
- Yalnızca doğrudan yolları kontrol etmek. İkinci örnekteki 0 ve 2 numaralı şehirler arasında 0 vardır ve yine de 1 numaralı şehir üzerinden aynı eyaleti paylaşırlar. Yalnızca doğrudan yollara dayalı herhangi bir sayım bunu gözden kaçırır; örneğin farklı satırları saymak, orada 3 yerine 5 verir.
- 1'leri sayıp ikiye bölmek. Bu, eyaletleri değil yolları sayar: Birbirine bağlı üç şehrin üç yolu ve bir eyaleti vardır.
- Union-find'de, yalnızca iki kök farklı olduğunda değil, her 1'de sayıyı azaltmak. Zaten birleştirilmiş bir grubun içindeki bir yol sayıyı değiştirmemelidir.
- Kökler yerine ebeveynleri karşılaştırmak. Ağaçta daha derinde olan bir şehir varsa,
parent[i] == parent[j]aynı gruptaki iki şehir için false olabilir; her zamanfind(i)ilefind(j)'yi karşılaştırın. parent[j] = find(i)örneğindeki gibi, kökü yerinejşehrini bağlamak.jzaten bir gruptaysa, o grubun geri kalanı birleştirmeden kopar.- Büyük graflarda özyineleme kullanmak. Özyinelemeli bir arama ya da union by rank kullanılmayan özyinelemeli bir
find, zincir şeklindeki bir grafta şehir başına bir düzey ilerler. 150 şehirde sorun olmaz, ancak 10^5 şehirde yığın taşmasına neden olur.
Sıkça sorulan sorular4
Number of Provinces algoritmasının zaman karmaşıklığı nedir?
Graf araması veya union-find kullanıldığında zaman karmaşıklığı O(n²) olur; çünkü ikisi de n × n matrisinin her girdisini bir kez okur. Union-find, ters Ackermann fonksiyonu olan α(n) çarpanını ekler; bu değer gerçek girdiler için en fazla 4'tür. Ek alan, ziyaret edildi işaretleri ya da ebeveyn ve rank dizileri için O(n)'dir.
Number of Provinces için DFS, BFS veya union-find mı kullanmalısınız?
Üçü de O(n²) zamanda aynı sayıyı döndürür. Matrisin tamamı tek seferde verildiğinde yazması en kolay olan DFS veya BFS’dir. Yollar birer birer geldiğinde ya da iki şehrin aynı eyalete bağlı olup olmadığını da yanıtlamanız gerektiğinde union-find daha iyi bir araçtır; çünkü her yolu ve her soruyu yeni bir arama yapmadan, sabite yakın zamanda işler.
Birleşim-bulma yapısında yol sıkıştırma ve rütbeye göre birleştirme ne işe yarar?
Rütbeye göre birleştirme, iki grup birleştiğinde daha kısa ağacı daha uzun olanın altına bağlar; bu da her ağacın yüksekliğini en fazla log n ile sınırlar. Yol sıkıştırma, find işlevinin üzerinden geçtiği her düğümün doğrudan kökü göstermesini sağlar; böylece bu düğümlerden yapılan sonraki aramalar tek adımda tamamlanır. Her ikisi birlikte kullanıldığında, m işlemden oluşan herhangi bir dizinin maliyeti O(m α(n)) olur; bu da doğrusal zamana yakın bir sürede çalışır.
Eyalet Sayısı, Ada Sayısı'ndan nasıl farklıdır?
İkisi de bağlı bileşenleri sayar. Number of Islands probleminde grafik bir ızgaradır, her karenin en fazla dört komşusu vardır ve işlem O(rows × cols) sürer. Burada grafik bir komşuluk matrisi olarak verilir: herhangi bir şehir başka herhangi bir şehre bağlanabilir ve bir şehrin komşularını listelemek için n girdiden oluşan tam bir satırı okursun.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def findCircleNum(isConnected):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Beklenen
2