Sambungan Berlebihan dan Pengesanan Kitaran
Kesan sisi yang mencipta kitaran dalam graf tidak berarah dengan menggunakan union pada setiap sisi dan memeriksa sama ada dua nod sudah bersambung.
Sambungan Berlebihan dan Pengesanan Kitaran ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Apakah Sambungan Berlebihan?
Masalah Sambungan Berlebihan (LeetCode 684) memberikan anda sebuah pokok dengan n nod dan satu sisi tambahan yang membentuk tepat satu kitaran. Tugas anda ialah mencari sisi yang, apabila dibuang, memulihkan pokok tersebut. Jika terdapat beberapa jawapan, kembalikan jawapan yang terakhir dalam senarai input.
Sebuah pokok dengan n nod mempunyai tepat n-1 sisi dan bersifat terhubung tanpa kitaran. Menambah satu lagi sisi akan menghasilkan tepat satu kitaran. Sisi tambahan (sisi berlebihan) menghubungkan dua nod yang sudah berada dalam komponen yang sama — situasi klasik untuk pengesanan kitaran dengan DSU.
# Example
# n=5, edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
# Adding edge [2,3] creates cycle 1-2-3-1
# So [2,3] is the redundant connection
# Key insight: process edges one by one with DSU
# The FIRST edge where both endpoints are already connected is the redundant one
print('Tree property: n nodes, n-1 edges, no cycles')
print('Adding 1 edge: n nodes, n edges, exactly 1 cycle')
print('DSU approach: find the edge that connects already-connected nodes')Pengesanan Kitaran dengan DSU
DSU mengesan kitaran secara semula jadi: sebelum menambah sisi (u, v), semak sama ada find(u) == find(v). Jika kedua-duanya berkongsi akar, kedua-duanya sudah terhubung — penambahan sisi ini menghasilkan kitaran. Inilah sisi berlebihan.
Pendekatan ini berfungsi untuk graf tidak berarah. Bagi setiap sisi, kita sama ada berjaya melakukan union terhadap dua komponen (belum ada kitaran) atau mengesan bahawa kedua-dua titik hujungnya sudah berada dalam komponen yang sama (kitaran ditemui). Kerumitan masa ialah O(n × alpha(n)), hampir O(n).
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1)) # 1-indexed
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # same component => cycle found
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v] # this edge creates the cycle
edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
print(find_redundant_connection(edges)) # [2, 3]Menelusuri Algoritma
Mari kita telusuri [[1,2],[1,3],[2,3]] langkah demi langkah. Pada mulanya, setiap nod ialah komponennya sendiri: {1}, {2}, {3}.
- Sisi [1,2]: find(1)=1, find(2)=2, berbeza — lakukan union terhadapnya. Komponen: {1,2}, {3}
- Sisi [1,3]: find(1)=akar, find(3)=3, berbeza — lakukan union terhadapnya. Komponen: {1,2,3}
- Sisi [2,3]: find(2)=akar, find(3)=akar — akar yang sama! Kitaran dikesan. Kembalikan [2,3].
Algoritma ini memproses sisi mengikut susunan dan mengembalikan sisi pertama yang melengkapkan kitaran. Oleh sebab masalah ini menjamin hanya satu sisi tambahan, sisi ini sentiasa merupakan sisi berlebihan yang betul.
def find_redundant_trace(edges):
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
print(f'Edge ({u},{v}): find({u})={pu}, find({v})={pv}', end=' => ')
if pu == pv:
print('CYCLE DETECTED!')
return [u, v]
parent[pv] = pu
print('merged')
return []
result = find_redundant_trace([[1,2],[1,3],[2,3]])
print('Redundant edge:', result)Pengesanan Kitaran dalam Graf Tidak Berarah dengan DFS
Alternatif kepada DSU untuk pengesanan kitaran dalam graf tidak berarah ialah DFS dengan penjejakan induk. Semasa DFS, jika kita sampai ke nod yang sudah dilawati dan nod itu bukan induk langsung bagi nod semasa, kita telah menemui sisi belakang — yang menunjukkan kewujudan kitaran.
Walau bagaimanapun, pendekatan DFS memerlukan masa O(V + E) dan mengembalikan sama ada kitaran wujud, tetapi tidak mudah menentukan sisi khusus yang berlebihan. DSU lebih sesuai untuk masalah yang meminta anda mengenal pasti sisi berlebihan tertentu kerana anda menemuinya secara semula jadi apabila union gagal.
from collections import defaultdict
def has_cycle_dfs(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb == parent:
continue # skip the edge we came from
if nb in visited:
return True # back edge => cycle
if dfs(nb, node):
return True
return False
for node in range(1, n + 1):
if node not in visited:
if dfs(node, -1):
return True
return False
print(has_cycle_dfs(3, [[1,2],[1,3],[2,3]])) # True
print(has_cycle_dfs(3, [[1,2],[1,3]])) # FalsePengesanan Kitaran dalam Graf Berarah
Untuk graf berarah, pengesanan kitaran dengan DSU tidak berfungsi secara langsung kerana sisi mempunyai arah. Sebaliknya, gunakan DFS dengan penandaan tiga warna: putih (belum dilawati), kelabu (dalam laluan DFS semasa), dan hitam (telah diproses sepenuhnya). Sisi belakang ke nod kelabu menunjukkan kewujudan kitaran.
Dalam graf tidak berarah, mana-mana sisi belakang bermaksud terdapat kitaran. Dalam graf berarah, sisi silang ke nod hitam bukanlah kitaran — hanya sisi belakang ke nod kelabu yang dianggap kitaran. Perbezaan ini penting dan diuji dalam masalah penjadualan kursus.
def has_cycle_directed(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 0=white(unvisited), 1=grey(in stack), 2=black(done)
color = [0] * (n + 1)
def dfs(node):
color[node] = 1 # grey: currently visiting
for nb in graph[node]:
if color[nb] == 1:
return True # back edge to grey node => cycle
if color[nb] == 0:
if dfs(nb):
return True
color[node] = 2 # black: fully processed
return False
for node in range(1, n + 1):
if color[node] == 0:
if dfs(node):
return True
return False
from collections import defaultdict
print(has_cycle_directed(3, [[1,2],[2,3],[3,1]])) # True: 1->2->3->1
print(has_cycle_directed(3, [[1,2],[1,3],[2,3]])) # FalseSambungan Berlebihan II: Varian Graf Berarah
LeetCode 685 mengembangkan masalah ini kepada graf berarah yang setiap nodnya mempunyai tepat satu induk (membentuk pokok berakar dengan satu sisi tambahan). Dua kes boleh berlaku: sama ada sebuah nod mempunyai dua induk (darjah masuk 2), atau terdapat kitaran tanpa mana-mana nod yang mempunyai dua induk.
Penyelesaian ini terlebih dahulu menyemak nod yang mempunyai darjah masuk 2. Jika ditemui, salah satu daripada dua sisi masuknya mestilah jawapannya. Kemudian, pengesanan kitaran dengan DSU menentukan sisi calon yang perlu dibuang. Pendekatan dua fasa ini mengendalikan semua kes dengan betul.
def find_redundant_directed(edges):
n = len(edges)
parent_map = {} # node -> its parent in the input
candidate1 = candidate2 = None
for u, v in edges:
if v in parent_map: # v already has a parent
candidate1 = [parent_map[v], v] # earlier edge
candidate2 = [u, v] # later edge
else:
parent_map[v] = u
# DSU cycle detection, skipping candidate2 if it exists
dsu = list(range(n + 1))
def find(x):
while dsu[x] != x: dsu[x] = dsu[dsu[x]]; x = dsu[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
dsu[px] = py; return True
for u, v in edges:
if candidate2 and [u, v] == candidate2: continue # skip candidate2
if not union(u, v): # cycle found without candidate2
return candidate1 if candidate1 else [u, v]
return candidate2 # no cycle when excluding candidate2 => candidate2 is redundant
print(find_redundant_directed([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_directed([[1,2],[2,3],[3,4],[4,1],[1,5]])) # [4,1]Kesahan Graf Selepas Pembuangan Sisi
Selepas mengenal pasti sisi berlebihan, kita boleh mengesahkan hasilnya dengan menyemak bahawa pembuangan sisi tersebut meninggalkan pokok yang sah: tepat n-1 sisi, semua nod terhubung dan tiada kitaran. Untuk masalah temu duga ini, DSU menjaminnya secara semula jadi — jika kita mengembalikan sisi yang menyebabkan union gagal, membuangnya meninggalkan tepat n-1 sisi yang berjaya menjalani union, dan sisi-sisi itu membentuk pokok rentangan.
Jaminan ini menjadikan DSU begitu kemas untuk masalah ini: union yang berjaya membina pokok secara beransur-ansur, manakala union yang gagal mengenal pasti satu sisi yang tidak tergolong di dalamnya.
def verify_tree(n, edges, removed_edge):
parent = list(range(n + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
components = n
for u, v in edges:
if [u, v] == removed_edge:
continue # skip the removed edge
pu, pv = find(u), find(v)
if pu == pv:
print('CYCLE DETECTED after removal! Wrong answer.')
return False
parent[pv] = pu
components -= 1
if components != 1:
print(f'Graph not connected ({components} components). Wrong answer.')
return False
print('Valid tree after removing edge:', removed_edge)
return True
edges = [[1,2],[1,3],[2,3]]
verify_tree(3, edges, [2,3])
verify_tree(3, edges, [1,2]) # wrong removalAnalisis Kerumitan Masa dan Ruang
Penyelesaian sambungan berlebihan berasaskan DSU memproses setiap satu daripada n sisi tepat sekali, dan setiap operasi union/find memerlukan O(alpha(n)) secara diamortisasikan. Jumlah masa: O(n × alpha(n)), secara berkesan O(n).
Kerumitan ruang ialah O(n) untuk tatasusunan induk dan pangkat. Ini adalah optimum — sekurang-kurangnya anda perlu membaca semua n sisi dan menyimpan sedikit keadaan bagi setiap nod. Bandingkan dengan pendekatan naif yang menjalankan DFS selepas setiap penyisipan sisi: masa O(n²) dan ruang O(n + E).
# Summary of complexities
complexity = {
'Naive (DFS after each edge)': {'time': 'O(n^2)', 'space': 'O(n)'},
'DSU (path compression + rank)': {'time': 'O(n * alpha(n))', 'space': 'O(n)'},
'Sorting + DSU (Kruskal style)': {'time': 'O(n log n)', 'space': 'O(n)'},
}
for approach, costs in complexity.items():
print(f'{approach}:')
print(f' Time: {costs["time"]}')
print(f' Space: {costs["space"]}')
print()
print('alpha(n) <= 4 for all practical n, so DSU is effectively O(n).')Kes Pinggir: Gelung Kendiri
Sisi gelung kendiri [u, u] serta-merta menghasilkan kitaran kerana kedua-dua titik hujungnya ialah nod yang sama. Dalam DSU, find(u) == find(u) sentiasa benar, jadi union gagal serta-merta dan [u, u] dikembalikan sebagai sisi berlebihan.
Kebanyakan kekangan masalah menjamin tiada gelung kendiri, tetapi kod yang teguh harus mengendalikannya. Pelaksanaan DSU mengendalikannya secara semula jadi tanpa sebarang kes khas — semakan kitaran if find(u) == find(v) mengesannya sebelum sebarang union dicuba. Sentiasa sahkan dengan input kes pinggir seperti gelung satu nod dan input bersaiz minimum.
def find_redundant_robust(edges):
n = len(edges)
parent = list(range(n + 1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv:
return [u, v] # handles self-loops too: u==v => pu==pv always
parent[pv] = pu
return []
# Self-loop test
print(find_redundant_robust([[1,2],[2,2]])) # [2,2] self-loop
# Minimum tree test
print(find_redundant_robust([[1,2],[2,3],[1,3]])) # [1,3]
# Standard test
print(find_redundant_robust([[1,2],[1,3],[2,3],[2,4],[3,5]])) # [2,3]Menggeneralisasikan Pengesanan Kitaran Merentas Algoritma
Pelbagai algoritma mengesan kitaran, dan setiap satunya sesuai untuk senario yang berbeza:
- DSU: graf tidak berarah, ketibaan sisi dalam talian, O(alpha(n)) bagi setiap sisi — terbaik untuk mengira atau mencari sisi berlebihan
- DFS dengan penjejakan induk: graf tidak berarah, semua sisi diketahui dari awal, O(V+E) — terbaik apabila anda memerlukan laluan kitaran
- DFS tiga warna: graf berarah, mengesan sisi belakang, O(V+E) — terbaik untuk penjadualan kursus dan pengisihan topologi
- Pengisihan topologi (Kahn): graf berarah, mengesan kitaran melalui nod dengan darjah masuk bukan sifar yang masih tinggal — terbaik apabila anda turut memerlukan susunan
# When to use which cycle-detection method:
# Problem type => preferred algorithm
problems = [
('Redundant Connection (undirected)', 'DSU'),
('Course Schedule (directed)', 'DFS three-color or Kahn topological sort'),
('Detect cycle in undirected graph', 'DFS with parent tracking or DSU'),
('Find cycle members in directed graph', 'DFS three-color + backtrack'),
('Online graph edges with cycle check', 'DSU'),
('Minimum spanning tree validity', 'DSU (Kruskal)'),
]
for problem, solution in problems:
print(f'{problem}\n => {solution}\n')Penyelesaian Lengkap dengan Kes Pinggir
Berikut ialah penyelesaian berkualiti produksi untuk Sambungan Berlebihan yang mengendalikan semua kes pinggir: nod berindeks 1, tepat satu sisi berlebihan dan jaminan bahawa pembuangannya meninggalkan pokok yang sah. Penyelesaian ini menggunakan DSU optimum dengan pembahagian laluan kepada separuh dan union mengikut pangkat.
Selepas menghantar penyelesaian, cuba soalan susulan ini: bagaimana jika graf boleh mempunyai beberapa sisi berlebihan? Anda perlu menjejaki semua sisi yang melengkapkan kitaran dan mengembalikan sisi terakhir dalam input — strategi tamak yang sama masih berfungsi kerana DSU memproses sisi mengikut susunan.
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v]
return [] # should never reach here given valid input
test_cases = [
[[1,2],[1,3],[2,3]],
[[1,2],[2,3],[3,4],[1,4],[1,5]],
[[1,2],[1,3],[2,3],[2,4],[3,5]],
]
for tc in test_cases:
print(find_redundant_connection(tc))Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Rumusan Pelajaran
Dalam pelajaran ini, anda mempelajari bahawa: sambungan berlebihan ialah sisi yang menghubungkan dua nod yang sudah terhubung dalam graf tidak berarah, DSU mengesannya dengan menyemak find(u) == find(v) sebelum union dan mengembalikan sisi tersebut, dan graf berarah memerlukan DFS tiga warna atau algoritma Kahn, bukannya DSU, untuk pengesanan kitaran. Seterusnya, kita menggunakan DSU pada masalah penggabungan akaun, yang e-melnya menjadi nod dan e-mel yang dikongsi antara akaun mencetuskan union.
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Sambungan Berlebihan dan Pengesanan Kitaran” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Sambungan Berlebihan dan Pengesanan Kitaran”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Sambungan Berlebihan dan Pengesanan Kitaran”?
Kesan sisi yang mencipta kitaran dalam graf tidak berarah dengan menggunakan union pada setiap sisi dan memeriksa sama ada dua nod sudah bersambung. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?
Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.
Berapa lamakah pelajaran “Sambungan Berlebihan dan Pengesanan Kitaran” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- DSU dengan Pemampatan Laluan
- Penyatuan Mengikut Pangkat dan Had Ackermann Songsang
- Sambungan Berlebihan dan Pengesanan Kitaran
- Penggabungan Akaun dan Komponen Terhubung