Redundant Connection

Q: Berapa kompleksitas waktu Redundant Connection?

Union-find menyelesaikannya dalam satu kali melewati n sisi: waktu O(n · α(n)), dengan α(n) paling banyak 4 dalam praktik, dan ruang O(n). Mengupas simpul daun juga memerlukan O(n). Mencoba setiap penghapusan dengan pencarian baru memerlukan O(n²).

SedangUnion-find Graf

+10

Sebuah jaringan awalnya berbentuk tree: n node, bernomor dari 1 sampai n, dihubungkan oleh n-1 edge tak berarah tanpa siklus. Kemudian, satu edge lagi ditambahkan di antara dua node yang tidak terhubung secara langsung, sehingga daftar edges kini berisi n edge dan tepat satu siklus.

Kembalikan sebuah edge yang dapat kamu hapus agar n-1 edge lainnya kembali membentuk tree. Jika beberapa edge bisa dihapus, kembalikan edge yang muncul paling akhir di edges, sebagai pasangan [a, b] persis seperti yang tertulis di sana.

Fungsi

findRedundantConnection(edges: integer-2d-array) → integer-array

edgesinteger-2d-array: n sisi tak berarah, masing-masing berupa pasangan [a, b] dari simpul bernomor mulai dari 1
Mengembalikaninteger-array: sisi siklus yang muncul terakhir di edges, ditulis persis seperti di sana

Batasan

3 ≤ n ≤ 5000, dengan n = edges.length
edges[i] = [a, b] dengan 1 ≤ a, b ≤ n dan a ≠ b
Tidak ada sisi yang muncul dua kali, dalam arah mana pun.
Sisi-sisi menghubungkan semua n simpul dan membentuk tepat satu siklus.

Contoh

Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Penjelasan: Tiga sisi membentuk segitiga 1, 2, 3, jadi menghapus salah satunya akan menyisakan pohon. [2, 3] berada di urutan terakhir dalam daftar.

Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
Penjelasan: Siklusnya adalah 1, 2, 3, 4, 1. Sisi [1, 5] tidak termasuk di dalamnya: jika sisi itu dihapus, node 5 akan terputus. Dari empat sisi siklus, [1, 4] muncul terakhir.

Pertanyaan lanjutan

Jika sisinya berarah dan graf aslinya berupa pohon berakar, sisi mana yang akan kamu hapus ketika sisi tambahan membuat sebuah simpul memiliki dua induk?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Menghapus sebuah edge akan menyisakan tree tepat ketika edge tersebut berada pada satu-satunya cycle dalam graph, jadi jawabannya adalah edge cycle yang muncul paling akhir dalam daftar. Union-find menemukannya dalam satu kali lintasan: tambahkan edge secara berurutan, dan edge pertama yang kedua ujungnya sudah terhubung adalah jawabannya.

Coba hapus setiap sisi, mulai dari sisi terakhir.

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Hapus satu sisi dan periksa apakah n-1 sisi lainnya membentuk pohon. Dengan n simpul dan n-1 sisi, semua sisi tersebut membentuk pohon tepat jika satu pencarian dari simpul 1 mencapai semua n simpul. Coba sisi-sisinya dari akhir daftar, sehingga penghapusan pertama yang berhasil adalah yang paling akhir. Simpan indeks setiap sisi dalam daftar ketetanggaan, lalu pencarian dapat melewati sisi yang dihapus tanpa membangun ulang apa pun.

Setiap percobaan adalah pencarian O(n) penuh, dan bisa ada n percobaan: hingga 2.5 × 10^7 langkah saat n = 5000.

Algoritma

Buat daftar adjacency yang menyimpan indeks edge yang menuju ke setiap tetangga.
Untuk skip dari indeks terakhir hingga 0, lakukan pencarian dari node 1 dan abaikan edge dengan indeks skip.
Hitung node yang dicapai oleh pencarian.
Jika pencarian mencapai semua n, kembalikan edges[skip].

def findRedundantConnection(edges):
    n = len(edges)
    # graph[x] holds (neighbour, index of the edge) for every edge at node x.
    graph = [[] for _ in range(n + 1)]
    for i, (u, v) in enumerate(edges):
        graph[u].append((v, i))
        graph[v].append((u, i))
    # Try leaving out each edge, the last one first.
    for skip in range(n - 1, -1, -1):
        # Without edge skip, can node 1 still reach all n nodes?
        seen = [False] * (n + 1)
        seen[1] = True
        stack = [1]
        reached = 1
        while stack:
            node = stack.pop()
            for nxt, i in graph[node]:
                if i != skip and not seen[nxt]:
                    seen[nxt] = True
                    reached += 1
                    stack.append(nxt)
        # n-1 edges that connect n nodes form a tree.
        if reached == n:
            return edges[skip]
    return []

Kupas daun-daunnya

Intuisi

Daun, yaitu simpul dengan satu sisi, tidak mungkin berada pada siklus, karena siklus masuk dan keluar dari setiap simpulnya. Menghapus daun dapat membuat tetangganya menjadi daun, jadi terus hapus daun sampai tidak ada yang tersisa. Simpul yang tersisa tepat merupakan siklus, karena setiap simpul siklus tetap memiliki dua sisi siklusnya. Pada contoh kedua, simpul 5 dihapus, simpul 1 tetap memiliki dua sisi, dan simpul 1 sampai 4 tersisa.

Setiap sisi antara dua simpul yang tersisa adalah sisi siklus, karena hubungan kedua antara simpul siklus akan membentuk siklus kedua. Jadi, telusuri edges dari akhir dan kembalikan sisi pertama yang kedua ujungnya masih tersisa.

Algoritma

Buat adjacency list dan hitung derajat setiap node.
Masukkan setiap node berderajat 1 ke dalam stack.
Keluarkan sebuah daun dari stack, tetapkan derajatnya menjadi 0, lalu kurangi derajat tetangganya yang tersisa; masukkan tetangga tersebut ke dalam stack saat derajatnya turun menjadi 1.
Saat stack kosong, node dengan derajat lebih dari 0 membentuk siklus.
Telusuri edges dari akhir dan kembalikan edge pertama yang kedua ujungnya masih tersisa.

def findRedundantConnection(edges):
    n = len(edges)
    graph = [[] for _ in range(n + 1)]
    degree = [0] * (n + 1)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1
    # A node with one edge cannot lie on the cycle. Remove it, and repeat.
    stack = [x for x in range(1, n + 1) if degree[x] == 1]
    while stack:
        leaf = stack.pop()
        degree[leaf] = 0
        for nxt in graph[leaf]:
            if degree[nxt] > 0:
                degree[nxt] -= 1
                if degree[nxt] == 1:
                    stack.append(nxt)
    # Only the cycle is left. Its edge that comes last in the list is the answer.
    for u, v in reversed(edges):
        if degree[u] > 0 and degree[v] > 0:
            return [u, v]
    return []

Union-find: sisi pertama yang membentuk perulangan

Intuisi

Tambahkan sisi sesuai urutan dalam list dan catat node mana saja yang terhubung. Sebelum siklus tertutup, setiap sisi menghubungkan dua bagian yang belum memiliki jalur di antaranya. Sisi pertama yang kedua ujungnya sudah terhubung akan menutup siklus. Sisi lain dalam siklus ditambahkan sebelumnya, jadi sisi siklus itulah yang muncul terakhir. Pada contoh kedua, [1, 4] menemukan bahwa node 1 dan 4 sudah terhubung, dan [1, 5] tidak pernah dibaca.

Union-find menyimpan satu array, parent; menelusuri pointer dari suatu node akan berakhir di root bagiannya. Menempatkan bagian yang lebih kecil di bawah bagian yang lebih besar, serta mengarahkan node ke kakek-neneknya saat find, menjaga rantainya tetap pendek. Setiap operasi pun memiliki biaya amortisasi O(α(n)), dengan α, fungsi invers Ackermann, paling banyak 4 untuk masukan nyata apa pun.

Algoritma

Arahkan setiap simpul dari 1 hingga n ke dirinya sendiri, parent[x] = x, lalu beri ukuran 1.
Telusuri edges secara berurutan. Untuk [u, v], cari akar dari u dan akar dari v.
Jika akarnya sama, [u, v] menutup siklus: kembalikan seperti yang tertulis.
Jika tidak, bagian yang lebih besar menyerap bagian yang lebih kecil: akarnya menjadi induk dari akar yang lebih kecil, lalu jumlahkan ukurannya.

def findRedundantConnection(edges):
    n = len(edges)
    parent = list(range(n + 1))  # every node starts as its own group
    size = [1] * (n + 1)

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        # u and v are already connected: this edge closes the cycle.
        if a == b:
            return [u, v]
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    return []

Jebakan dan kasus tepi

Mengembalikan sisi terakhir dari list. Pada contoh kedua, sisi itu adalah [1, 5], dan menghapusnya memutus simpul 5.
Memindai dari awal setelah mengupasnya. Ini mengembalikan sisi siklus paling awal, yaitu [1, 2] pada contoh kedua.
Mengurutkan atau membalik pasangan. Jika list berisi [3, 1], kembalikan [3, 1], bukan [1, 3].
Mengatur ukuran array untuk simpul 0 hingga n-1. Simpul diberi nomor mulai dari 1, jadi simpul n memerlukan array dengan n+1 slot.
Melakukan rekursi mengelilingi siklus. Proses ini dapat melewati semua 5000 simpul, lima kali batas rekursi default Python, jadi gunakan stack eksplisit dan perulangan di find.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Redundant Connection?

Union-find menyelesaikannya dalam satu kali melewati n sisi: waktu O(n · α(n)), dengan α(n) paling banyak 4 dalam praktik, dan ruang O(n). Mengupas simpul daun juga memerlukan O(n). Mencoba setiap penghapusan dengan pencarian baru memerlukan O(n²).

Sisi mana yang dapat dihapus agar tersisa sebuah pohon?

Tepatnya, sisi-sisi pada siklus. Masing-masing memiliki rute kedua yang menghubungkan kedua ujungnya melalui bagian siklus lainnya, sehingga menghapusnya membuat graf tetap terhubung. Sisi lainnya merupakan satu-satunya penghubung antara dua bagian graf, dan menghapusnya akan memisahkan kedua bagian tersebut.

Bisakah Redundant Connection diselesaikan dengan DFS?

Ya. Sebelum menambahkan setiap sisi, telusuri dari salah satu ujung melalui sisi-sisi yang sudah ditambahkan; sisi pertama yang ujung lainnya sudah dapat dijangkau adalah jawabannya. Cara ini membutuhkan O(n) untuk setiap sisi, atau O(n²) secara keseluruhan, sedangkan union-find menjawab pertanyaan yang sama dalam waktu hampir konstan.

def findRedundantConnection(edges):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

edges = [[1, 2], [1, 3], [2, 3]]

Output yang diharapkan

[2, 3]

Redundant Connection

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Coba hapus setiap sisi, mulai dari sisi terakhir.

Kupas daun-daunnya

Union-find: sisi pertama yang membentuk perulangan

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa