Graph Valid Tree

Q: Berapa kompleksitas waktu dari Graph Valid Tree?

O(n + m) dengan penelusuran depth-first, dengan m sebagai jumlah edge, dan O(n + m α(n)) dengan union-find. Keduanya memeriksa jumlah edge terlebih dahulu, sehingga graf dengan jumlah yang salah ditolak sebelum pencarian apa pun.

SedangUnion-find Graf

+10

Kamu mendapatkan n node, bernomor dari 0 hingga n-1, dan sebuah list edges yang berisi edge tak berarah. Setiap pasangan [a, b] menghubungkan node a dan node b.

Kembalikan true jika edge tersebut membentuk satu tree yang mencakup semua n node: setiap node dapat mencapai semua node lainnya, dan tidak ada siklus. Jika tidak, kembalikan false.

Fungsi

validTree(n: integer, edges: integer-2d-array) → boolean

ninteger: jumlah node, bernomor dari 0 sampai n-1
edgesinteger-2d-array: edge tak berarah, masing-masing berupa pasangan [a, b]
Mengembalikanboolean: true jika sisi-sisinya menghubungkan semua n simpul menjadi satu pohon, false jika tidak

Batasan

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] dengan 0 ≤ a, b ≤ n-1 dan a ≠ b
Tidak ada sisi yang muncul dua kali, dalam arah mana pun.

Contoh

Input: n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: true
Penjelasan: Node 0 terhubung ke node 1, 2, dan 3, sedangkan node 4 terhubung ke node 1. Empat sisi menghubungkan kelima node tanpa perulangan, jadi ini adalah tree.

Input: n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: false
Penjelasan: Sisi [1, 2], [2, 3], dan [1, 3] membentuk siklus 1, 2, 3, 1. Lima sisi pada lima simpul lebih banyak satu daripada jumlah sisi yang dapat dimiliki pohon.

Input: n = 4edges = [[0, 1], [1, 2], [2, 0]]
Output: false
Penjelasan: Ada 3 sisi, yaitu n-1, tetapi sisi-sisi itu membentuk siklus 0, 1, 2, 0, dan simpul 3 sama sekali tidak memiliki sisi.

Pertanyaan lanjutan

Jika graf bukan tree, berapa banyak edge yang harus kamu hapus, dan berapa banyak yang harus kamu tambahkan agar graf itu menjadi tree? Bisakah kamu menghitung keduanya dalam satu kali lintasan?

Petunjuk

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

0 dari 3 dibuka

Solusi

Pohon terhubung dan tidak memiliki siklus. Dengan tepat n-1 sisi, keduanya menjadi satu kondisi: graf seperti itu terhubung tepat ketika tidak memiliki siklus. Jadi, periksa jumlah sisi terlebih dahulu, lalu lakukan satu kali pencarian untuk memeriksa keterhubungan, atau biarkan union-find mendeteksi sisi yang menghubungkan dua simpul yang sudah terhubung.

Cari jalur sebelum setiap sisi

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tambahkan sisi satu per satu. Sebelum menambahkan [u, v], lakukan pencarian dari u melalui sisi yang sudah ditambahkan. Jika v dapat dijangkau, sisi baru itu menjadi rute kedua di antara keduanya dan membentuk siklus, seperti yang dilakukan [1, 3] pada contoh kedua. Jika tidak ada sisi yang membentuk siklus, graf tersebut adalah hutan, dan pencarian terakhir dari simpul 0 memberi tahu apakah graf itu merupakan satu pohon.

Setiap pemeriksaan mencari di seluruh graf yang sudah terbentuk. Pada jalur dengan 5001 simpul yang sisinya datang secara berurutan, pencarian mengunjungi 1 + 2 + ... + 5000 simpul, sekitar 12,5 juta.

Algoritma

Mulai dengan daftar ketetanggaan kosong untuk setiap simpul.
Untuk setiap sisi [u, v], lakukan pencarian dari u melalui sisi-sisi yang sudah ditambahkan. Jika pencarian mencapai v, kembalikan false.
Jika tidak, tambahkan sisi tersebut ke daftar kedua ujungnya.
Pada akhirnya, kembalikan apakah pencarian dari simpul 0 mencapai semua n simpul.

def reachable(graph, start):
    # Every node a search from start can reach, using the edges added so far.
    seen = [False] * len(graph)
    seen[start] = True
    stack = [start]
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                stack.append(nxt)
    return seen


def validTree(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        # A path from u to v already exists, so this edge closes a cycle.
        if reachable(graph, u)[v]:
            return False
        graph[u].append(v)
        graph[v].append(u)
    # No cycle anywhere. A tree also needs every node reachable from node 0.
    return all(reachable(graph, 0))

Hitung sisi-sisinya, lalu cari sekali

Intuisi

Mulai dari n node yang terpisah, lalu tambahkan edge satu per satu. Setiap edge menggabungkan dua grup sehingga jumlah grup berkurang satu, atau berada di dalam satu grup dan membentuk siklus. Untuk mencapai satu grup, diperlukan n-1 penggabungan. Jadi, kurang dari n-1 edge tidak dapat menghubungkan graph, sedangkan lebih dari itu pasti membentuk siklus: contoh kedua, 5 edge pada 5 node, gagal hanya berdasarkan jumlahnya.

Dengan tepat n-1 edge, graph berakhir sebagai satu grup saja jika setiap edge merupakan penggabungan, yaitu jika tidak ada edge yang membentuk siklus. Jadi, setelah jumlahnya tepat, periksa konektivitas saja: satu pencarian dari node 0 harus mencapai semua n node. Pada contoh ketiga, pencarian itu hanya mencapai 0, 1, dan 2. Dengan m = n-1, list dan pencarian memerlukan biaya O(n).

Algoritma

Jika edges.length tidak sama dengan n-1, kembalikan false.
Buat daftar adjacency, dengan menyimpan setiap edge di bawah kedua ujungnya.
Push node 0 ke dalam stack dan tandai sebagai sudah dikunjungi.
Pop node lalu push setiap tetangga yang belum dikunjungi, tandai dan hitung saat kamu memasukkannya.
Kembalikan apakah jumlahnya sama dengan n.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    # With n-1 edges, the graph is a tree exactly when it is connected.
    seen = [False] * n
    seen[0] = True
    stack = [0]
    reached = 1
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                reached += 1
                stack.append(nxt)
    return reached == n

Hitung sisi dan struktur union-find

Intuisi

Union-find menjawab pertanyaan tentang siklus untuk setiap edge tanpa pencarian. Setiap node awalnya menjadi kelompoknya sendiri. Untuk edge [u, v], cari root dari kedua ujungnya. Jika root berbeda, edge menghubungkan dua bagian, jadi gabungkan keduanya. Jika root sama, u dan v sudah terhubung dan edge tersebut membentuk siklus. Dengan n-1 edge yang semuanya menggabungkan kelompok, pada akhirnya n kelompok menjadi satu: sebuah tree.

Dua aturan menjaga rantai parent tetap pendek. Saat menggabungkan kelompok, root kelompok yang lebih kecil ditempatkan di bawah root kelompok yang lebih besar, sehingga dengan 10^4 node, tidak ada rantai yang melewati 13 langkah. Saat melakukan find, arahkan setiap node yang kamu lewati ke grandparent-nya. Secara bersama-sama, kedua aturan ini membuat biaya m operasi menjadi O(m α(n)), dengan α, fungsi Ackermann invers, paling banyak 4 di sini. Penggunaan ruang adalah O(n).

Algoritma

Jika edges.length bukan n-1, kembalikan false.
Tetapkan parent[x] = x dan ukuran grup 1 untuk setiap node.
Untuk setiap edge [u, v], ikuti parent dari u dan dari v hingga mencapai root masing-masing, lalu arahkan setiap node yang kamu lewati ke grandparent-nya.
Jika root-nya sama, kembalikan false.
Jika root-nya berbeda, hubungkan root grup yang lebih kecil ke root grup lainnya dan tambahkan ukurannya.
Jika setiap edge berhasil menggabungkan dua grup, kembalikan true.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    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)
        # The two ends are already joined: this edge closes a cycle.
        if a == b:
            return False
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    # n-1 merges with no cycle turn the n groups into one.
    return True

Jebakan dan kasus tepi

Hanya memeriksa adanya siklus. Tiga sisi terpisah pada enam simpul tidak memiliki siklus, tetapi membentuk tiga bagian.
Hanya memeriksa jumlah sisi. Contoh ketiga memiliki n-1 sisi, tetapi perulangan 0, 1, 2 menggunakan sisi yang dibutuhkan simpul 3.
Menyimpan setiap sisi hanya di bawah satu ujungnya. [1, 0] juga menghubungkan simpul 0 dan 1, dan pencarian dari simpul 0 tidak menemukan simpul 1.
Pengujian siklus depth-first yang tidak melewati parent. Setiap sisi mengarah langsung kembali ke simpul asal, jadi "bertemu tetangga yang sudah dikunjungi" terjadi pada setiap pohon.
Melakukan rekursi pada jalur panjang. Jalur yang terdiri dari 5001 simpul memiliki kedalaman 5000 pemanggilan, melampaui batas default Python sebesar 1000; gunakan stack eksplisit.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Graph Valid Tree?

O(n + m) dengan penelusuran depth-first, dengan m sebagai jumlah edge, dan O(n + m α(n)) dengan union-find. Keduanya memeriksa jumlah edge terlebih dahulu, sehingga graf dengan jumlah yang salah ditolak sebelum pencarian apa pun.

Mengapa pohon dengan n simpul memiliki n-1 sisi?

Bangun pohon mulai dari satu node, lalu tambahkan node lainnya satu per satu. Setiap node baru datang dengan tepat satu edge: tanpa edge, node itu akan terputus, sedangkan dengan dua edge, node itu akan membentuk siklus. Jadi, n node membutuhkan n-1 edge.

Bagaimana cara mendeteksi siklus dalam graf tak berarah?

Dengan union-find, sebuah sisi yang kedua ujungnya sudah memiliki root yang sama membentuk siklus. Dengan pencarian depth-first, siklus adalah tetangga yang sudah dikunjungi selain simpul asalmu, jadi kamu melacak parent setiap simpul. Union-find tidak memerlukan parent maupun adjacency list.

def validTree(n, edges):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

Output yang diharapkan

true

Graph Valid Tree

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Cari jalur sebelum setiap sisi

Hitung sisi-sisinya, lalu cari sekali

Hitung sisi dan struktur union-find

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa