Gereksiz Bağlantı ve Çevrim Belirleme
Her kenarda birleştirme uygulayıp iki düğümün zaten bağlı olup olmadığını kontrol ederek yönsüz grafikte çevrim oluşturan kenarı belirleyin.
Gereksiz Bağlantı ve Çevrim Belirleme, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Gereksiz Bağlantı Nedir
Gereksiz Bağlantı problemi (LeetCode 684) size n düğümlü bir ağaç ve tam olarak bir döngü oluşturan fazladan bir kenar verir. Göreviniz, kaldırıldığında ağacı yeniden oluşturan kenarı bulmaktır. Birden fazla yanıt varsa girdi listesindeki sonuncuyu döndürün.
n düğümlü bir ağaçta tam olarak n-1 kenar bulunur; ağaç bağlantılıdır ve döngü içermez. Bir kenar daha eklemek tam olarak bir döngü oluşturur. Eklenen (gereksiz) kenar, zaten aynı bileşende bulunan iki düğümü bağlar — bu, DSU ile döngü tespiti için klasik bir senaryodur.
# 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')DSU ile Döngü Tespiti
DSU döngüleri doğal biçimde tespit eder: (u, v) kenarını eklemeden önce find(u) == find(v) denetimini yapın. Aynı kökü paylaşıyorlarsa zaten bağlıdırlar; bu kenarı eklemek bir döngü oluşturur. Bu kenar gereksiz kenardır.
Bu yaklaşım yönsüz graflarda çalışır. Her kenar için ya iki bileşeni başarıyla union ederiz (henüz döngü yoktur) ya da her iki uç noktanın zaten aynı bileşende olduğunu tespit ederiz (döngü bulunur). Zaman karmaşıklığı O(n × alpha(n)), yani neredeyse O(n)'dir.
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]Algoritmayı Adım Adım İzleme
[[1,2],[1,3],[2,3]] örneğini adım adım izleyelim. Başlangıçta her düğüm kendi bileşenidir: {1}, {2}, {3}.
- Kenar [1,2]: find(1)=1, find(2)=2, farklı — union yapın. Bileşenler: {1,2}, {3}
- Kenar [1,3]: find(1)=kök, find(3)=3, farklı — union yapın. Bileşenler: {1,2,3}
- Kenar [2,3]: find(2)=kök, find(3)=kök — same kök! Döngü tespit edildi. [2,3] döndürülür.
Algoritma kenarları sırayla işler ve döngüyü tamamlayan ilk kenarı döndürür. Problem yalnızca bir fazladan kenar olduğunu garanti ettiği için bu her zaman doğru gereksiz kenardır.
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)DFS ile Yönsüz Graflarda Döngü Tespiti
Yönsüz graflarda döngü tespiti için DSU'ya alternatif olarak ebeveyn takibiyle DFS kullanılabilir. DFS sırasında zaten ziyaret edilmiş ve geçerli düğümün doğrudan ebeveyni olmayan bir düğüme ulaşırsak, bir geri kenar bulmuş oluruz; bu da bir döngü olduğunu gösterir.
Ancak DFS yaklaşımı O(V + E) zaman gerektirir ve bir döngünün var olup olmadığını döndürür; hangi belirli kenarın gereksiz olduğunu kolayca belirleyemez. Belirli gereksiz kenarı bulmanızı isteyen problemlerde DSU tercih edilir, çünkü union başarısız olduğunda bu kenarı doğal olarak bulursunuz.
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]])) # FalseYönlü Graflarda Döngü Tespiti
Yönlü graflarda DSU ile döngü tespiti, kenarların yönü olduğu için doğrudan çalışmaz. Bunun yerine üç renkle işaretleme kullanan DFS uygulayın: beyaz (ziyaret edilmemiş), gri (geçerli DFS yolunda) ve siyah (tamamen işlenmiş). Gri bir düğüme giden geri kenar, bir döngü olduğunu gösterir.
Yönsüz bir grafın her geri kenarı bir döngü anlamına gelir. Yönlü bir grafta siyah bir düğüme giden çapraz kenar döngü değildir — yalnızca gri düğümlere giden geri kenarlar döngü oluşturur. Bu ayrım kritiktir ve ders programı problemlerinde sınanır.
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]])) # FalseGereksiz Bağlantı II: Yönlü Grafik Varyantı
LeetCode 685, problemi her düğümün tam olarak bir ebeveyne sahip olduğu yönlü graflara genişletir (bir fazladan kenar içeren köklü bir ağaç). İki durum ortaya çıkar: ya bir düğümün iki ebeveyni vardır (giriş derecesi 2) ya da hiçbir düğümün iki ebeveyni olmadan bir döngü vardır.
Çözüm önce giriş derecesi 2 olan düğümleri kontrol eder. Böyle bir düğüm bulunursa, iki gelen kenarından biri yanıt olmalıdır. Ardından DSU ile döngü tespiti, iki aday kenardan hangisinin kaldırılacağını belirler. Bu iki aşamalı yaklaşım tüm durumları doğru biçimde ele alır.
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]Kenar Kaldırıldıktan Sonra Grafın Geçerliliği
Gereksiz kenarı belirledikten sonra, kaldırılmasının geriye geçerli bir ağaç bıraktığını denetleyerek sonucu doğrulayabiliriz: tam olarak n-1 kenar, tüm düğümler bağlı ve hiç döngü yok. Mülakat probleminde DSU bunu doğal olarak garanti eder — union işlemi başarısız olan kenarı döndürürsek, onu kaldırdığımızda başarıyla union edilen ve bir örten ağaç oluşturan tam olarak n-1 kenar kalır.
DSU'nun bu problem için bu kadar temiz olmasının nedeni budur: başarılı union işlemleri ağacı adım adım oluşturur, başarısız union ise ağaca ait olmayan tek kenarı belirler.
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 removalZaman ve Alan Karmaşıklığı Analizi
DSU tabanlı gereksiz bağlantı çözümü n kenarın her birini tam olarak bir kez işler ve her union/find işlemi O(alpha(n)) amortize maliyete sahiptir. Toplam süre: O(n × alpha(n)), yani pratikte O(n).
Alan karmaşıklığı, ebeveyn ve derece dizileri için O(n)'dir. Bu optimaldir — en azından tüm n kenarı okumalı ve düğüm başına bir miktar durum saklamalısınız. Bunu, her kenar eklemesinden sonra DFS çalıştıran saf yaklaşımla karşılaştırın: O(n²) zaman ve O(n + E) alan.
# 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).')Özel Durum: Kendine Döngü
[u, u] biçimindeki kendine döngü kenarı, her iki uç noktası da same düğüm olduğu için hemen bir döngü oluşturur. DSU'da find(u) == find(u) her zaman doğrudur; bu nedenle union hemen başarısız olur ve [u, u] gereksiz kenar olarak döndürülür.
Çoğu problem kısıtı kendine döngülere izin vermez, ancak sağlam kod bunları ele almalıdır. DSU uygulaması bunu doğal olarak, özel bir durum gerektirmeden ele alır — if find(u) == find(v) döngü denetimi herhangi bir union denenmeden önce durumu yakalar. Tek düğümlü döngüler ve en küçük boyutlu girdiler gibi kenar durumu girdileriyle her zaman doğrulama yapın.
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]Algoritmalar Genelinde Döngü Tespitini Genelleştirme
Birden çok algoritma döngü tespit eder; her biri farklı senaryolara uygundur:
- DSU: yönsüz graflar, çevrim içi kenar gelişi, kenar başına O(alpha(n)) — sayma veya gereksiz kenarı bulma için en iyisi
- Ebeveyn takibiyle DFS: yönsüz graflar, tüm kenarlar baştan biliniyor, O(V+E) — döngü yoluna ihtiyaç duyduğunuzda en iyisi
- Üç renkli DFS: yönlü graflar, geri kenarları tespit etme, O(V+E) — ders programı ve topolojik sıralama için en iyisi
- Topolojik sıralama (Kahn algoritması): yönlü graflar, geriye kalan giriş derecesi sıfır olmayan düğümler üzerinden döngü tespiti — sıralamaya da ihtiyaç duyduğunuzda en iyisi
# 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')Kenar Durumlarıyla Tam Çözüm
Gereksiz Bağlantı için tüm kenar durumlarını ele alan, üretim kalitesinde bir çözüm aşağıdadır: 1 tabanlı düğümler, tam olarak bir gereksiz kenar ve bu kenarın kaldırılmasının geçerli bir ağaç bırakacağı garantisi. Çözüm, yol yarılama ve dereceye göre union kullanan optimal DSU'yu kullanır.
Gönderimin ardından şu devam sorusunu deneyin: grafın birden fazla gereksiz kenarı olsaydı ne olurdu? Döngüyü tamamlayan tüm kenarları izlemeniz ve girdi listesindeki sonuncuyu döndürmeniz gerekirdi — DSU kenarları sırayla işlediği için aynı açgözlü strateji yine işe yarar.
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))Hızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayışınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: gereksiz bağlantı, yönsüz bir grafta zaten bağlı olan iki düğümü bağlayan kenardır, DSU bunu union işleminden önce find(u) == find(v) denetimini yapıp bu kenarı döndürerek tespit eder ve yönlü graflarda döngü tespiti için DSU yerine üç renkli DFS veya Kahn algoritması gerekir. Sırada DSU'yu, düğümlerin e-postalar olduğu ve ortak e-postaların hesaplar arasında union işlemlerini tetiklediği hesapları birleştirme problemine uygulayacağız.
Sıkça Sorulan Sorular
“Gereksiz Bağlantı ve Çevrim Belirleme” dersi ücretsiz mi?
Evet — “Gereksiz Bağlantı ve Çevrim Belirleme” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Gereksiz Bağlantı ve Çevrim Belirleme” dersinde ne öğreneceğim?
Her kenarda birleştirme uygulayıp iki düğümün zaten bağlı olup olmadığını kontrol ederek yönsüz grafikte çevrim oluşturan kenarı belirleyin. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Gereksiz Bağlantı ve Çevrim Belirleme” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Yol Sıkıştırmalı DSU
- Dereceye Göre Birleştirme ve Ters Ackermann Sınırı
- Gereksiz Bağlantı ve Çevrim Belirleme
- Hesapları Birleştirme ve Bağlantılı Bileşenler