Number of Provinces
n şehir vardır; bunlar 0 ile n-1 arasında numaralandırılmıştır. isConnected[i][j], bir yol i şehri ile j şehrini doğrudan bağlıyorsa 1, aksi hâlde 0 değerini alır. Yollar çift yönlüdür, bu nedenle matris simetriktir ve her şehir kendisine bağlıdır.
Bir eyalet, doğrudan veya diğer şehirler üzerinden birbirlerine ulaşabilen ve gruptan dışarıya giden yolu olmayan şehirlerden oluşan bir gruptur. Eyalet sayısını döndürün.
Fonksiyon
- isConnectedinteger-2d-array
- n × n matris; bir yolun iki şehri doğrudan bağladığı yerde 1
- Döndürürinteger
- il sayısı
Kısıtlar
1 ≤ n ≤ 150, buradan = isConnected.lengthisConnected[i].length = nisConnected[i][j]0veya1değerindedirisConnected[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 numaralı şehre giden bir yolu, 1 numaralı şehrin ise 2 numaralı şehre giden bir yolu var. İki çift arasında yol bulunmadığı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 doğrudan bir yol yoktur, ancak ikisi de 1 numaralı şehre bağlıdır; bu nedenle 0, 1 ve 2 numaralı şehirler tek bir eyalet oluşturur. 3 ve 4 numaralı şehirlerin yolu yoktur ve her biri ayrı bir eyalettir: toplam 3.
Ek soru
Artık her yol belirli bir günde açılıyor. Tüm şehirlerin tek bir ile 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öşegenin dışındaki her
1değerini de iki nokta arasındaki bir çizgi olarak çizin. Bu resimde bir il nasıl görünür?Bir eyalet, bağlı bir bileşendir: İki şehrin arasındaki 0, birbirlerinden ayrı oldukları anlamına gelmez; çünkü üçüncü bir şehir onları birbirine bağlayabilir. Daha önceki hiçbir aramanın ulaşmadığı bir şehirden yeni bir aramaya kaç kez başlamanız gerektiğini sayın.
Başka bir yol: şehir başına bir grup olacak şekilde
ngrupla başlayın ve köşegenin üzerindeki 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 zamanlı hâle getirir.
Çözüm
Matris, yönsüz bir grafiği tanımlar: şehirler düğümlerdir ve her 1 bir kenardır. Bir eyalet, bağlantılı bir bileşendir ve üçüncü bir şehir her ikisini de birbirine bağladığında iki şehir arasındaki 0 onları ayırmaz. Ziyaret edilmemiş her şehirden başlatılan bir arama veya her kenar üzerinde union-find kullanımı, bileşenleri O(n²) içinde sayar.
Henüz ziyaret edilmemiş her şehirden derinlik öncelikli arama
Sezgi
İşaretlenmemiş bir şehir, daha önce saydığınız bir eyalete ait olamaz; çünkü her arama, eyaletin tamamını işaretler. Bu yüzden yeni bir eyalet başlatır. Arama, matrisin satırlarını izler: ikinci örnekte, 0. şehirden yapılan arama 1. şehre ulaşır ve ardından 1. şehrin satırı 2. şehre ulaşır; oysa 0. satırda 2. şehir için 0 vardır.
Her şehir yığından bir kez çıkarılır ve n girişli satırını okur; dolayısıyla matrisi bir kez okursunuz: O(n²) zaman. İşaretler ve yığın en fazla n şehir tutar; bu yüzden ek alan O(n)'dir.
Algoritma
- Her şehir için bir görülme bayrağı oluşturun ve sayacı 0 olarak ayarlayın.
- Şehirleri sırayla dolaşın ve daha önce görülmüş olan şehirleri atlayın.
- Henüz görülmemiş bir şehirde sayacı 1 artırın, şehri işaretleyin ve bir yığına ekleyin.
- Yığında şehir olduğu sürece bir şehri çıkarın ve o satırında 1 olan ve henüz görülmemiş her şehri, eklerken işaretleyerek yığına ekleyin.
- Sayıcıyı döndürün.
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 Union-find
Sezgi
n şehirle başlayın; her şehir için bir il olsun. Köşegenin üzerindeki her 1, iki şehrin birlikte olduğunu belirtir: Grupları farklıysa onları birleştirin ve sayıyı bir azaltın. İkinci örnekte sayı 5'ten başlar; (0, 1) şehir 0 ile 1'i birleştirir, (1, 2) şehir 2'yi gruplarına katar ve geriye 3 il kalır.
Union-find, her grubu bir ağaç olarak saklar: parent[c] bir basamak yukarıyı gösterir ve find her iki şehri de aynı köke kadar izlediğinde şehirler aynı gruptadır. Kendi hâline bırakılırsa, birleştirmeler her find işleminin O(n) adımda yürüdüğü uzun bir yol oluşturabilir. Sıraya göre birleştirme, kısa ağacı uzun olanın altına bağlar; böylece hiçbir yol log n'den uzun olmaz. Yol sıkıştırma, find işleminin üzerinden geçtiği her şehri doğrudan köke yönlendirir. Birlikte, her find işleminin amortize maliyetini O(α(n)) yaparlar ve α(n) pratikte en fazla 4'tür.
Algoritma
- Her şehir için
parent[c] = cverank[c] = 0ayarla ve sayıyınolarak belirle. isConnected[i][j] = 1olan heri < jçifti içinivejköklerini bul.findiçinde köke kadar ilerle, ardından yolu tekrar geç ve üzerindeki her şehri köke bağla.- Kökler farklıysa, daha düşük rütbeli kökü diğerinin altına bağla, eşitlik durumunda rütbeyi 1 artır ve sayıdan 1 çıkar.
- Sayıyı döndür.
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
- Yalnızca doğrudan yolları dikkate almak. İkinci örnekteki 0 ve 2 numaralı şehirlerin arasında 0 var ve yine de aynı eyaleti paylaşıyorlar.
- 1'leri sayıp ikiye bölmek. Birbirine bağlı üç şehirde üç yol ve bir eyalet vardır.
- Union-find'de, yalnızca iki kök farklı olduğunda değil, her 1 için sayıyı azaltmak.
parent[i]ileparent[j]değerlerini karşılaştırmak. Aynı gruptaki iki şehrin, biri daha derinde olduğunda farklı ebeveynleri olabilir;find(i)ilefind(j)değerlerini karşılaştır.parent[j] = find(i)örneğindeki gibi doğrudanjşehrini eklemek.jzaten bir gruptaysa, o grubun geri kalanı birleştirme dışında kalır.
Sıkça sorulan sorular3
Number of Provinces'in zaman karmaşıklığı nedir?
O(n²), ister grafik araması ister union-find kullanılsın, çünkü ikisi de n × n matrisinin her girdisini bir kez okur. Union-find, pratikte en fazla 4 olan ters Ackermann fonksiyonu α(n) çarpanını ekler. Ek alan O(n)'dir.
Number of Provinces için DFS, BFS yoksa union-find mi kullanmalısınız?
Üçü de O(n²) zamanda aynı sayıyı döndürür. Yazması en kısa olan DFS veya BFS'dir. Her yanıtın neredeyse sabit zaman aldığı “bu iki şehir aynı ili mi paylaşıyor” türünde birçok soruyu da yanıtlamanız gerektiğinde union-find daha iyi bir araçtır.
Number of Provinces, Number of Islands'tan nasıl farklıdır?
İkisi de bağlantı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) olur. Buradaki grafik bir komşuluk matrisidir: herhangi bir şehir başka herhangi bir şehre bağlanabilir ve bir şehrin komşularını listelemek, n girdi içeren tam bir satırı okumayı gerektirir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def findCircleNum(isConnected):
# Kodu buraya yazınTest #1
Test #2
Argüman
isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Beklenen Çıktı
2