Strongly Connected Components
Graf berarah memiliki n simpul, bernomor dari 0 hingga n-1, dan daftar edges, dengan [from, to] sebagai sisi dari simpul from ke simpul to.
Komponen terhubung kuat adalah kelompok simpul terbesar yang setiap simpulnya dapat mencapai semua simpul lainnya dengan mengikuti sisi. Setiap simpul termasuk tepat dalam satu komponen, dan simpul yang tidak berada pada siklus mana pun membentuk komponen tersendiri. Kembalikan jumlah komponen terhubung kuat.
Fungsi
- ninteger
- jumlah node
- edgesinteger-2d-array
- sisi berarah, masing-masing sebagai [from, to]
- Mengembalikaninteger
- jumlah komponen yang terhubung kuat
Batasan
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]dengan0 ≤ from, to < ndanfrom ≠ to- Tidak ada edge yang muncul dua kali.
Contoh
- Input
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- Output
- 3
- Penjelasan
- Node 0, 1, dan 2 membentuk perulangan, sehingga node-node tersebut dapat saling mencapai. Node 3 dan 4 saling menunjuk. Node 5 dapat mencapai 4, tetapi tidak ada yang kembali ke 5, sehingga node 5 berdiri sendiri: 3 komponen.
- Input
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- Output
- 4
- Penjelasan
- Node 0 dan 1 saling menunjuk dan membentuk satu komponen. Sisi dari 2 ke 3 hanya mengarah satu arah, jadi 2 dan 3 terpisah, dan node 4 tidak memiliki sisi sama sekali: 4 komponen.
Pertanyaan lanjutan
Berapa sedikit sisi yang perlu kamu tambahkan agar seluruh graf menjadi satu komponen terhubung kuat?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Dua simpul berbagi komponen tepat ketika masing-masing dapat mencapai simpul lainnya. Pencarian dari setiap simpul dapat mengujinya, tetapi pencarian itu menelusuri sisi yang sama berulang kali. Apa yang dapat diberitahukan oleh satu pencarian mendalam tentang tempat dimulainya sebuah komponen?
Beri nomor pada node sesuai urutan pertama kali pencarian mendalam mencapainya. Untuk setiap node, lacak juga
low: nomor terkecil yang dapat dicapainya dengan menelusuri pohon pencarian ke bawah, lalu mengikuti satu edge kembali ke node yang komponennya masih terbuka. Node yanglow-nya sama dengan nomornya sendiri adalah node pertama dalam komponennya.Simpan simpul yang sudah dikunjungi dalam sebuah tumpukan. Saat penelusuran simpul selesai dengan
lowsama dengan nomornya sendiri, keluarkan simpul dari tumpukan hingga simpul tersebut: simpul-simpul itu membentuk satu komponen, jadi hitung komponen itu. Salah satu pengujian membuat penelusuran mencapai kedalaman 5000 simpul, jadi gunakan tumpukanmu sendiri yang berisi frame (simpul, sisi berikutnya), alih-alih menggunakan rekursi.
Solusi
Susutkan setiap komponen menjadi satu titik, lalu komponen-komponen itu membentuk graf tanpa siklus. Algoritma Kosaraju dan Tarjan memanfaatkan hal itu untuk menemukan setiap komponen dalam O(n + E), dengan E adalah jumlah sisi.
Cari maju dan mundur dari setiap node
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Node u dan v berada dalam komponen yang sama tepat ketika masing-masing dapat mencapai yang lain. Jadi, untuk node s yang belum memiliki komponen, telusuri ke depan mengikuti edge dan ke belakang mengikuti edge yang dibalik. Node yang ditemukan oleh kedua penelusuran tersebut adalah komponen node itu. Pada contoh pertama, penelusuran ke depan dari 0 menemukan node 0 hingga 4, sedangkan penelusuran ke belakang menemukan 0, 1, dan 2, jadi {0, 1, 2} adalah satu komponen.
Setiap komponen memerlukan dua penelusuran pada sebagian besar graf. Pada rantai dengan 5000 edge yang melewati 5001 node, setiap node menjadi komponennya sendiri, dan penelusuran mengunjungi sekitar 2.5 × 10^7 node.
Algoritma
- Buat daftar sisi keluar dan sisi masuk untuk setiap node.
- Ambil node berikutnya
syang belum memiliki komponen, lalu hitung satu komponen baru. - Tandai node yang dapat dicapai
smelalui sisi keluar, dan node yang dapat mencapaismelalui sisi masuk. - Setiap node yang ditandai oleh kedua pencarian menjadi bagian dari komponen
s. Setelah setiap node memiliki komponen, kembalikan jumlahnya.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countAlgoritma Kosaraju: dua lintasan
Intuisi
Dalam graf komponen, ada komponen yang menjadi sink, tanpa sisi yang keluar darinya, dan pencarian yang dimulai di dalamnya menemukan tepat komponen itu. Algoritma Kosaraju mengurutkan pencarian agar masing-masing berjalan seperti itu.
Lintasan pertama mencatat setiap node saat pencarian depth-first-nya selesai. Lintasan kedua mencari di graf terbalik, yang memiliki komponen yang sama, dimulai dari node yang paling akhir selesai. Jika ada sisi dari komponen B ke C, node terakhir B selesai setelah semua node di C selesai. Jadi, saat lintasan kedua mencapai C, semua komponen yang memiliki sisi menuju C sudah ditetapkan, dan pencarian di graf terbalik tidak dapat keluar dari C.
Dalam contoh pertama, node selesai dalam urutan 4, 3, 2, 1, 0, 5. Lintasan kedua mengumpulkan {5}, lalu {0, 1, 2}, kemudian {3, 4}.
Algoritma
- Buat daftar sisi keluar dan sisi masuk.
- Jalankan pencarian mendalam iteratif dari setiap simpul yang belum dikunjungi, lalu tambahkan setiap simpul ke
ordersaat penelusurannya selesai. - Telusuri
orderdari akhir. Untuk setiap simpul yang belum memiliki komponen, hitung satu komponen baru dan lakukan pencarian dari simpul tersebut melalui sisi masuk, lalu tetapkan komponen itu ke setiap simpul yang belum memiliki komponen dan berhasil dijangkau. Kembalikan jumlahnya.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countAlgoritma Tarjan: satu kali lintasan dengan nilai low
Intuisi
Jalankan satu penelusuran depth-first dan beri nomor pada setiap node sesuai urutan kamu mencapainya: index-nya. Pertahankan stack berisi node yang sudah dikunjungi dan komponennya masih terbuka, serta sebuah nilai low: index terkecil yang dicapai sebuah node dengan menuruni pohon pencarian lalu kembali satu edge ke node pada stack tersebut.
Saat penelusuran sebuah node selesai dengan low yang lebih kecil daripada index, berarti sesuatu di bawahnya naik kembali ke node terbuka yang lebih awal, jadi node itu tetap berada di stack. Jika nilainya sama, node tersebut adalah node pertama yang dimasuki penelusuran dalam komponennya: keluarkan node dari stack sampai node itu, lalu hitung satu komponen. Edge menuju node yang sudah dikeluarkan mengarah ke komponen yang sudah selesai dan tidak dapat menjangkau kembali, jadi edge itu diabaikan.
Pada contoh pertama, 3 mengeluarkan {4, 3} dan 0 mengeluarkan {2, 1, 0} dari stack. Edge dari node 5 mengarah ke node 4 yang sudah dikeluarkan, jadi node 5 dikeluarkan sendiri.
Algoritma
- Untuk setiap simpul yang belum dikunjungi, berikan indeks berikutnya, atur
lowke nilai yang sama, dorong simpul tersebut ke stack simpul, lalu dorong frame (node, first edge). - Jika simpul pada frame teratas masih memiliki sisi yang belum ditelusuri, ikuti sisi tersebut: target yang belum dikunjungi mendapat indeks dan frame, sedangkan target yang ada di stack simpul menurunkan
low[node]ke indeksnya. - Jika tidak, keluarkan frame dan turunkan
lowinduknya kelow[node]. Jikalow[node]sama denganindex[node], keluarkan simpul dari stack simpul hingga simpul tersebut, lalu hitung satu komponen.
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
Jebakan dan kasus tepi
- Melupakan simpul yang tidak memiliki sisi. Pada contoh kedua, simpul 4 tidak muncul pada sisi mana pun dan tetap merupakan komponen.
- Menurunkan
lowmelalui simpul mana pun yang sudah dikunjungi, bukan hanya simpul yang ada di stack. Pada contoh pertama, sisi5 → 4kemudian membuat 5 tidak bisa menutup komponennya. - Memperlakukan sisi sebagai dua arah. Ini menghitung komponen terhubung: contoh pertama akan menghasilkan 1, bukan 3.
- Melakukan rekursi di Python. Siklus melalui 5000 simpul menumpuk 5000 pemanggilan, lima kali batas default 1000. Gunakan stack frame milikmu sendiri.
- Menjalankan lintasan kedua Kosaraju pada sisi asli, atau sesuai urutan simpul pertama kali dikunjungi. Keduanya akan menggabungkan komponen yang hanya dapat saling mencapai dalam satu arah.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu untuk menemukan komponen terhubung kuat?
Waktu O(n + E) dengan algoritma Kosaraju atau Tarjan, karena setiap simpul dan sisi ditangani sebanyak jumlah konstan. Keduanya menggunakan ruang O(n + E) untuk daftar sisi dan tumpukan pencarian.
Haruskah kamu menggunakan algoritma Kosaraju atau Tarjan?
Algoritma Kosaraju terdiri dari dua penelusuran sederhana dan lebih sulit untuk keliru. Algoritma Tarjan hanya memerlukan satu penelusuran dan tidak memerlukan graf terbalik, dengan konsekuensi harus mengelola low.
Apa perbedaan antara komponen terhubung kuat dan komponen terhubung?
Komponen terhubung mengabaikan arah edge: dua node berada dalam komponen yang sama jika ada jalur yang menghubungkan keduanya. Komponen terhubung kuat mengharuskan setiap node dapat mencapai node lainnya. Contoh pertama terdiri dari satu komponen terhubung, tetapi tiga komponen terhubung kuat.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def countSCC(n, edges):
# Tulis kodemu di siniTes #1
Tes #2
Argumen
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
Output yang diharapkan
3