0Pricing
DSA Interview Prep · Pelajaran

Koneksi Berlebih dan Deteksi Siklus

Deteksi sisi yang menciptakan siklus dalam graf tak berarah dengan menerapkan union pada setiap sisi dan memeriksa apakah dua simpul sudah terhubung

Koneksi Berlebih dan Deteksi Siklus adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa Itu Koneksi Redundan?

Masalah Koneksi Redundan (LeetCode 684) memberi Anda sebuah pohon dengan n simpul dan satu sisi tambahan yang membentuk tepat satu siklus. Tugas Anda adalah menemukan sisi yang, jika dihapus, akan mengembalikan graf tersebut menjadi pohon. Jika ada beberapa jawaban, kembalikan jawaban terakhir dalam daftar input.

Sebuah pohon dengan n simpul memiliki tepat n-1 sisi dan terhubung tanpa siklus. Menambahkan satu sisi lagi akan membentuk tepat satu siklus. Sisi tambahan (redundan) tersebut menghubungkan dua simpul yang sudah berada dalam komponen yang sama — skenario klasik deteksi siklus 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')

Deteksi Siklus dengan DSU

DSU mendeteksi siklus secara alami: sebelum menambahkan sisi (u, v), periksa apakah find(u) == find(v). Jika keduanya memiliki akar yang sama, keduanya sudah terhubung — penambahan sisi ini akan membentuk siklus. Sisi tersebut adalah sisi redundan.

Pendekatan ini berlaku untuk graf tak berarah. Untuk setiap sisi, kita berhasil melakukan union pada dua komponen (belum ada siklus), atau mendeteksi bahwa kedua titik ujungnya sudah berada dalam komponen yang sama (siklus ditemukan). Kompleksitas waktunya adalah O(n × alpha(n)), yang hampir sama dengan 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 Algoritme

Mari kita telusuri [[1,2],[1,3],[2,3]] langkah demi langkah. Pada awalnya, setiap simpul merupakan komponennya sendiri: {1}, {2}, {3}.

  • Sisi [1,2]: find(1)=1, find(2)=2, berbeda — lakukan union. Komponen: {1,2}, {3}
  • Sisi [1,3]: find(1)=akar, find(3)=3, berbeda — lakukan union. Komponen: {1,2,3}
  • Sisi [2,3]: find(2)=akar, find(3)=akar — akar sama! Siklus terdeteksi. Kembalikan [2,3].

Algoritme memproses sisi sesuai urutannya dan mengembalikan sisi pertama yang menyelesaikan sebuah siklus. Karena masalah ini menjamin hanya ada satu sisi tambahan, sisi tersebut selalu merupakan sisi redundan yang benar.

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)

Deteksi Siklus dalam Graf Tak Berarah dengan DFS

Alternatif DSU untuk deteksi siklus dalam graf tak berarah adalah DFS dengan pelacakan induk. Selama DFS, jika kita mencapai simpul yang sudah dikunjungi dan bukan merupakan induk langsung dari simpul saat ini, berarti kita menemukan sisi balik — yang menunjukkan adanya siklus.

Namun, pendekatan DFS memerlukan waktu O(V + E) dan mengembalikan apakah sebuah siklus ada, tetapi tidak dengan mudah menunjukkan sisi redundan tertentu. DSU lebih disukai untuk masalah yang meminta Anda mengidentifikasi sisi redundan tertentu karena sisi tersebut ditemukan secara alami ketika operasi 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]]))        # False

Deteksi Siklus dalam Graf Berarah

Untuk graf berarah, deteksi siklus dengan DSU tidak dapat digunakan secara langsung karena sisi memiliki arah. Sebagai gantinya, gunakan DFS dengan penandaan tiga warna: putih (belum dikunjungi), abu-abu (berada dalam jalur DFS saat ini), dan hitam (telah diproses sepenuhnya). Sisi balik menuju simpul abu-abu menunjukkan adanya siklus.

Dalam graf tak berarah, setiap sisi balik berarti ada siklus. Dalam graf berarah, sisi silang menuju simpul hitam bukanlah siklus — hanya sisi balik menuju simpul abu-abu yang merupakan siklus. Perbedaan ini sangat penting dan diuji dalam masalah penjadwalan 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]]))  # False

Koneksi Redundan II: Varian Graf Berarah

LeetCode 685 memperluas masalah ini ke graf berarah, dengan setiap simpul memiliki tepat satu induk (membentuk pohon berakar dengan satu sisi tambahan). Ada dua kemungkinan: sebuah simpul memiliki dua induk (derajat masuk 2), atau terdapat siklus tanpa ada simpul yang memiliki dua induk.

Solusinya terlebih dahulu memeriksa simpul dengan derajat masuk 2. Jika ditemukan, salah satu dari dua sisi masuknya harus menjadi jawaban. Kemudian deteksi siklus dengan DSU menentukan sisi kandidat mana yang harus dihapus. Pendekatan dua tahap ini menangani semua kemungkinan dengan benar.

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]

Validitas Graf Setelah Penghapusan Sisi

Setelah mengidentifikasi sisi redundan, kita dapat memverifikasi hasilnya dengan memeriksa bahwa penghapusannya menyisakan pohon yang valid: tepat n-1 sisi, semua simpul terhubung, dan tidak ada siklus. Untuk keperluan masalah wawancara ini, DSU secara alami menjamin hal tersebut — jika kita mengembalikan sisi yang membuat union gagal, penghapusannya menyisakan tepat n-1 sisi yang berhasil di-union, dan sisi-sisi tersebut membentuk pohon merentang.

Jaminan inilah yang membuat DSU sangat sederhana untuk masalah ini: union yang berhasil membangun pohon secara bertahap, sedangkan union yang gagal mengidentifikasi satu-satunya sisi yang tidak termasuk 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 removal

Analisis Kompleksitas Waktu dan Ruang

Solusi koneksi redundan berbasis DSU memproses setiap sisi dari n sisi tepat satu kali, dan setiap operasi union/find membutuhkan O(alpha(n)) secara diamortisasi. Total waktu: O(n × alpha(n)), yang secara efektif sama dengan O(n).

Kompleksitas ruang adalah O(n) untuk larik induk dan peringkat. Ini optimal — setidaknya Anda harus membaca semua n sisi dan menyimpan sejumlah informasi untuk setiap simpul. Bandingkan dengan pendekatan naif yang menjalankan DFS setelah setiap penyisipan sisi: waktu 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).')

Kasus Khusus: Gelung Diri

Sisi gelung [u, u] langsung membentuk siklus karena kedua titik ujungnya merupakan simpul yang sama. Dalam DSU, find(u) == find(u) selalu benar, sehingga operasi union langsung gagal dan [u, u] dikembalikan sebagai sisi redundan.

Sebagian besar batasan masalah menjamin tidak ada sisi gelung, tetapi kode yang tangguh harus tetap menanganinya. Implementasi DSU secara alami menangani kasus ini tanpa kasus khusus apa pun — pemeriksaan siklus if find(u) == find(v) menangkapnya sebelum operasi union dilakukan. Selalu lakukan verifikasi dengan masukan kasus khusus seperti gelung satu simpul dan masukan berukuran 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]

Menggeneralisasi Deteksi Siklus Lintas Algoritme

Berbagai algoritme dapat mendeteksi siklus, dan masing-masing sesuai untuk skenario yang berbeda:

  • DSU: graf tak berarah, sisi datang secara daring, O(alpha(n)) per sisi — terbaik untuk menghitung atau menemukan sisi redundan
  • DFS dengan pelacakan induk: graf tak berarah, semua sisi diketahui sejak awal, O(V+E) — terbaik ketika Anda memerlukan jalur siklus
  • DFS tiga warna: graf berarah, mendeteksi sisi balik, O(V+E) — terbaik untuk masalah penjadwalan kursus dan pengurutan topologis
  • sort topologis (milik Kahn): graf berarah, mendeteksi siklus melalui simpul berderajat masuk tak nol yang tersisa — terbaik ketika Anda juga memerlukan urutan
# 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')

Solusi Lengkap dengan Kasus Khusus

Berikut solusi berkualitas produksi untuk Koneksi Redundan yang menangani semua kasus khusus: simpul berindeks mulai dari 1, tepat satu sisi redundan, dan jaminan bahwa penghapusan sisi tersebut menyisakan pohon yang valid. Solusi ini menggunakan DSU optimal dengan pembagian jalur dan union berdasarkan peringkat.

Setelah mengirimkan solusi, cobalah pertanyaan lanjutan berikut: bagaimana jika graf dapat memiliki beberapa sisi redundan? Anda perlu melacak semua sisi yang melengkapi siklus dan mengembalikan sisi terakhir dalam input — strategi pemilihan bertahap yang sama tetap berlaku karena DSU memproses sisi sesuai urutannya.

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))

Pemeriksaan Singkat

Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.

Rangkuman Pelajaran

Dalam pelajaran ini Anda mempelajari bahwa: koneksi redundan adalah sisi yang menghubungkan dua simpul yang sudah terhubung dalam graf tak berarah, DSU mendeteksinya dengan memeriksa find(u) == find(v) sebelum union lalu mengembalikan sisi tersebut, dan graf berarah memerlukan DFS tiga warna atau algoritme Kahn, bukan DSU, untuk deteksi siklus. Selanjutnya, kita akan menerapkan DSU pada masalah penggabungan akun, dengan alamat surel sebagai simpul dan alamat surel yang sama antar-akun memicu operasi union.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Koneksi Berlebih dan Deteksi Siklus” gratis?

Ya — teks lengkap “Koneksi Berlebih dan Deteksi Siklus” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Koneksi Berlebih dan Deteksi Siklus”?

Deteksi sisi yang menciptakan siklus dalam graf tak berarah dengan menerapkan union pada setiap sisi dan memeriksa apakah dua simpul sudah terhubung Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?

Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Koneksi Berlebih dan Deteksi Siklus” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. DSU dengan Kompresi Jalur
  2. Union Berdasarkan Rank dan Batas Invers Ackermann
  3. Koneksi Berlebih dan Deteksi Siklus
  4. Penggabungan Akun dan Komponen Terhubung
← Kembali ke DSA Interview Prep