Number of Provinces
Ada n kota, bernomor 0 sampai n-1. isConnected[i][j] bernilai 1 jika sebuah jalan menghubungkan kota i dan kota j secara langsung, dan 0 jika tidak. Jalan berlaku dua arah, jadi matriksnya simetris, dan setiap kota terhubung dengan dirinya sendiri.
Provinsi adalah kelompok kota yang semuanya dapat saling menjangkau, secara langsung atau melalui kota lain, tanpa ada jalan yang mengarah ke luar kelompok tersebut. Kembalikan jumlah provinsi.
Fungsi
- isConnectedinteger-2d-array
- matriks n × n, bernilai 1 jika sebuah jalan menghubungkan dua kota secara langsung
- Mengembalikaninteger
- jumlah provinsi
Batasan
1 ≤ n ≤ 150, dengann = isConnected.lengthisConnected[i].length = nisConnected[i][j]bernilai0atau1isConnected[i][i] = 1isConnected[i][j] = isConnected[j][i]
Contoh
- Input
- isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
- Output
- 2
- Penjelasan
- Kota 0 memiliki jalan menuju kota 3, dan kota 1 memiliki jalan menuju kota 2. Tidak ada jalan yang menghubungkan kedua pasangan tersebut, jadi ada 2 provinsi.
- Input
- 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]]
- Output
- 3
- Penjelasan
- Kota 0 dan 2 tidak memiliki jalan langsung, tetapi keduanya terhubung ke kota 1, sehingga kota 0, 1, dan 2 membentuk satu provinsi. Kota 3 dan 4 tidak memiliki jalan dan masing-masing menjadi satu provinsi: totalnya 3.
Pertanyaan lanjutan
Setiap jalan kini dibuka pada hari tertentu. Bisakah kamu menemukan hari pertama saat semua kota menjadi bagian dari satu provinsi?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Gambarkan setiap kota sebagai titik dan setiap
1di luar diagonal sebagai garis antara dua titik. Seperti apa bentuk sebuah provinsi dalam gambar itu?Provinsi adalah komponen terhubung: angka 0 di antara dua kota tidak berarti keduanya terpisah, karena kota ketiga dapat menghubungkan keduanya. Hitung berapa kali kamu harus memulai pencarian baru dari kota yang belum pernah dicapai oleh pencarian sebelumnya.
Cara lain: mulai dengan
nkelompok, satu untuk setiap kota, lalu gabungkan kelompokidanjuntuk setiap angka 1 di atas diagonal. Penggabungan dua kelompok yang berbeda mengurangi jumlah kelompok sebanyak satu. Struktur union-find dengan kompresi jalur membuat setiap penggabungan memerlukan waktu yang hampir konstan.
Solusi
Matriks ini menggambarkan graf tak berarah: kota adalah simpul dan setiap 1 adalah sisi. Provinsi adalah komponen terhubung, dan nilai 0 di antara dua kota tidak memisahkan keduanya jika kota ketiga menghubungkan keduanya. Pencarian dari setiap kota yang belum dikunjungi, atau union-find atas setiap sisi, menghitung komponen dalam O(n²).
Pencarian depth-first dari setiap kota yang belum dikunjungi
Intuisi
Kota yang belum ditandai tidak mungkin termasuk dalam provinsi yang sudah kamu hitung, karena setiap pencarian menandai seluruh provinsinya. Jadi, kota itu memulai provinsi baru. Pencarian mengikuti baris-baris matriks: pada contoh kedua, pencarian dari kota 0 mencapai kota 1, lalu baris kota 1 mencapai kota 2, meskipun baris 0 memiliki nilai 0 untuk kota 2.
Setiap kota dikeluarkan dari tumpukan satu kali dan membaca barisnya yang berisi n entri, jadi kamu membaca matriks satu kali: waktu O(n²). Penanda dan tumpukan menampung paling banyak n kota, jadi ruang tambahan adalah O(n).
Algoritma
- Buat flag penanda untuk setiap kota dan tetapkan jumlahnya ke 0.
- Telusuri kota-kota secara berurutan dan lewati kota yang sudah ditandai.
- Untuk kota yang belum ditandai, tambahkan 1 ke jumlah, tandai kota tersebut, lalu dorong ke stack.
- Selama stack masih berisi kota, keluarkan satu kota, lalu dorong setiap kota pada barisnya yang bernilai 1 dan belum ditandai, sambil menandainya saat didorong.
- Kembalikan jumlahnya.
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 provincesUnion-find dengan kompresi jalur dan penggabungan berdasarkan peringkat
Intuisi
Mulailah dengan n provinsi, satu untuk setiap kota. Setiap angka 1 di atas diagonal menunjukkan bahwa dua kota tergabung: jika kelompoknya berbeda, gabungkan keduanya dan kurangi jumlahnya satu. Dalam contoh kedua, jumlahnya dimulai dari 5, (0, 1) menggabungkan kota 0 dan 1, (1, 2) memasukkan kota 2 ke kelompok mereka, dan tersisa 3 provinsi.
Union-find menyimpan setiap kelompok sebagai pohon: parent[c] menunjuk satu langkah ke atas, dan dua kota berada dalam kelompok yang sama ketika find menelusuri keduanya hingga mencapai akar yang sama. Jika dibiarkan, penggabungan dapat membentuk satu jalur panjang yang harus ditelusuri oleh setiap find dalam O(n) langkah. Union berdasarkan rank menempatkan pohon yang lebih pendek di bawah pohon yang lebih tinggi, sehingga tidak ada jalur yang lebih panjang dari log n. Kompresi jalur membuat setiap kota yang dilewati find langsung menunjuk ke akar. Jika digabungkan, keduanya membuat setiap find memiliki kompleksitas amortisasi O(α(n)), dan dalam praktiknya α(n) paling besar 4.
Algoritma
- Tetapkan
parent[c] = cdanrank[c] = 0untuk setiap kota, lalu tetapkan jumlahnya ken. - Untuk setiap pasangan
i < jdenganisConnected[i][j] = 1, cari akar dariidanj. - Di
find, telusuri ke atas hingga mencapai akar, lalu telusuri jalur itu sekali lagi dan arahkan setiap kota di jalur tersebut ke akar. - Jika akarnya berbeda, pasangkan akar dengan peringkat lebih rendah di bawah akar lainnya, tambahkan 1 ke peringkat jika peringkatnya sama, lalu kurangi jumlahnya sebanyak 1.
- Kembalikan jumlahnya.
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
Jebakan dan kasus tepi
- Hanya mengandalkan jalan langsung. Kota 0 dan 2 pada contoh kedua memiliki nilai 0 di antara keduanya, tetapi tetap berada di provinsi yang sama.
- Menghitung jumlah angka 1 lalu membaginya dengan dua. Tiga kota yang semuanya terhubung satu sama lain memiliki tiga jalan dan satu provinsi.
- Dalam union-find, mengurangi hitungan setiap kali menemukan angka 1, bukan hanya ketika kedua root berbeda.
- Membandingkan
parent[i]denganparent[j]. Dua kota dalam satu grup bisa memiliki parent yang berbeda jika salah satunya berada lebih dalam. Bandingkanfind(i)denganfind(j). - Menghubungkan kota
jitu sendiri, seperti padaparent[j] = find(i). Jikajsudah berada dalam sebuah grup, anggota grup lainnya tidak ikut digabungkan.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu Number of Provinces?
O(n²) dengan pencarian graf atau union-find, karena keduanya membaca setiap entri matriks n × n satu kali. Union-find menambahkan faktor α(n), yaitu fungsi Ackermann invers, yang dalam praktiknya paling besar 4. Ruang tambahan adalah O(n).
Haruskah kamu menggunakan DFS, BFS, atau union-find untuk Number of Provinces?
Ketiganya mengembalikan jumlah yang sama dalam waktu O(n²). DFS atau BFS adalah yang paling singkat untuk ditulis. Union-find adalah alat yang lebih baik ketika kamu juga harus menjawab banyak pertanyaan seperti "apakah kedua kota ini berada di provinsi yang sama", karena setiap jawaban membutuhkan waktu yang hampir konstan.
Apa perbedaan Number of Provinces dan Number of Islands?
Keduanya menghitung komponen terhubung. Dalam Number of Islands, grafnya berbentuk kisi, setiap kotak memiliki paling banyak empat tetangga, dan jumlah pengerjaannya adalah O(rows × cols). Di sini grafnya berupa matriks ketetanggaan: setiap kota dapat terhubung ke kota mana pun, dan untuk mencantumkan tetangga satu kota, kamu perlu membaca satu baris penuh yang berisi n entri.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def findCircleNum(isConnected):
# Tulis kodemu di siniTes #1
Tes #2
Argumen
isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Output yang diharapkan
2