. Sambungan berlebihan

684. Sambungan berlebihan

Kesukaran: Medium

Topik

: carian kedalaman-pertama, carian lebar-pertama, cari kesatuan, graf

Dalam masalah ini, pokok adalah graf yang tidak diarahkan yang disambungkan dan tidak mempunyai kitaran.

Anda diberi graf yang bermula sebagai pokok dengan nod N yang dilabelkan dari 1 hingga N, dengan satu kelebihan tambahan ditambah. Kelebihan tambahan mempunyai dua yang berbeza simpang yang dipilih dari 1 hingga n, dan bukan kelebihan yang sudah ada. Grafik diwakili sebagai tepi array panjang n di mana tepi [i] = [a _i , b _i ] menunjukkan bahawa terdapat kelebihan antara node a _i dan b _i dalam graf.

kembali kelebihan yang boleh dikeluarkan supaya graf yang dihasilkan adalah pokok nod n . Sekiranya terdapat banyak jawapan, kembalikan jawapan yang berlaku terakhir dalam input .

Contoh 1:

• input: edges = [[1,2], [1,3], [2,3]]
• output: [2,3]

Contoh 2:

input:
• edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
output:
• [1,4]

Kekangan:

n == edges.length

• 3 & lt; = n & lt; = 1000
• tepi [i] .length == 2
• 1 & lt; = a
i
• & lt; b _i & lt; = edges.length ₃ tidak ada tepi berulang.
• Grafik yang diberikan disambungkan. Penyelesaian:
masalah
• Redundant Connection
meminta kita untuk mengenal pasti kelebihan dalam graf yang boleh dikeluarkan untuk menjadikan graf menjadi pokok yang sah. Pokok adalah graf yang tidak diarahkan yang disambungkan dan acyclic. Kami diberi graf yang bermula sebagai pokok tetapi diubahsuai dengan menambahkan satu kelebihan tambahan. Matlamat kami adalah untuk mencari dan mengembalikan kelebihan tambahan ini.

Mata utama

graf adalah

tidak diarahkan dan disambungkan

.

Grafik yang dihasilkan selepas mengeluarkan kelebihan yang berlebihan mestilah tidak mempunyai kitaran.

1. Jawapannya harus mengembalikan kelebihan yang muncul terakhir dalam input, dalam kes pelbagai penyelesaian yang sah. Grafik boleh mempunyai paling banyak satu kitaran kerana kelebihan tambahan tunggal.
Pendekatan
3. Pendekatan melibatkan menggunakan carian kedalaman (DFS)
untuk mengesan kitaran:

Perwakilan senarai adjacency

:

• Gunakan senarai adjacency untuk mewakili graf. Struktur ini sesuai untuk melaksanakan DFS dengan cekap.

Pengesanan kitaran melalui DFS :

• Sebelum menambahkan kelebihan ke graf, gunakan DFS untuk memeriksa sama ada sudah ada jalan di antara kedua -dua simpang tepi. Sekiranya ada, menambah kelebihan ini akan membentuk kitaran.

Mengembalikan kelebihan :

• Jika kitaran dikesan, kembalikan kelebihan semasa sebagai sambungan berlebihan.

Merancang

1. menghuraikan tepi input.
2. Mengekalkan senarai adjacency untuk menjejaki sambungan grafik secara dinamik.
3. untuk setiap kelebihan:
   • Gunakan fungsi DFS rekursif untuk memeriksa sama ada jalan wujud di antara kedua -dua simpang.
   • Jika jalan wujud, kembalikan kelebihan sebagai sambungan yang berlebihan.
   • Jika tidak, tambahkan kelebihan ke senarai adjacency.
4. Kembalikan hasil kosong jika tiada kelebihan berlebihan ditemui (walaupun ini tidak akan berlaku mengikut kekangan masalah).

mari kita melaksanakan penyelesaian ini dalam php: 684. Sambungan berlebihan

<?php /**
 * @param Integer[][] $edges
 * @return Integer[]
 */
function findRedundantConnection($edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to perform DFS and check connectivity
 *
 * @param $src
 * @param $target
 * @param $visited
 * @param $adjList
 * @return bool
 */
private function isConnected($src, $target, &$visited, &$adjList) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$edges1 = [[1,2],[1,3],[2,3]];
$edges2 = [[1,2],[2,3],[3,4],[1,4],[1,5]];

print_r(findRedundantConnection($edges1)) . "\n"; // Output: [2,3]
print_r(findRedundantConnection($edges2)) . "\n"; // Output: [1,4]
?>

Penjelasan:

1. pelaksanaan DFS :

   • Mula dari satu nod dan berulang -ulang melawat jiran -jirannya.
   • Gunakan array yang dikunjungi untuk mengelakkan nod mengkaji semula.
   • Jika nod sasaran dicapai semasa traversal, jalan wujud.

2. Tambahan tepi :

   • Jika tiada jalan wujud di antara simpul tepi, tambahkan kelebihan ke senarai adjacency dan teruskan ke tepi seterusnya.

3. kelebihan berlebihan :

   • Jika jalan sudah ada, kembalikan kelebihan semasa kerana ia membentuk kitaran.

Contoh Walkthrough

Contoh 1:

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

Langkah -langkah :

1. memulakan senarai adjacency sebagai [].
2. Proses tepi:
   • Tambah [1, 2] → Graf: {1: [2], 2: [1]}
   • Tambah [1, 3] → Graf: {1: [2, 3], 2: [1], 3: [1]}
   • Semak [2, 3]: DFS mencari jalan → kembali [2, 3].

output : [2, 3]

Contoh 2:

input : edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]

Langkah -langkah :

1. memulakan senarai adjacency sebagai [].
2. Proses tepi:
   • Tambah [1, 2] → Graf: {1: [2], 2: [1]}
   • Tambah [2, 3] → Graf: {1: [2], 2: [1, 3], 3: [2]}
   • Tambah [3, 4] → Graf: {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}
   • Semak [1, 4]: DFS mencari jalan → kembali [1, 4].

output : [1, 4]

Kerumitan masa

1. DFS Traversal :

   • Untuk setiap kelebihan, kami melakukan DFS untuk memeriksa sambungan.
   • kes terburuk: o (v e) , di mana v adalah bilangan simpang dan e adalah bilangan tepi.

2. Jumlah kerumitan :

   • Oleh kerana kita melakukan DFS untuk setiap kelebihan, kerumitan keseluruhan ialah o (e × (v e)) .

3. Kerumitan ruang :

   • Senarai Adjacency: o (v e) .
   • Array yang Dikunjungi: o (v) .
   • total: o (v e) .

Output untuk contoh

Contoh 1:

input : [[1, 2], [1, 3], [2, 3]]

output : [2, 3]

Contoh 2:

input : [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]

output : [1, 4]

Masalahnya boleh diselesaikan dengan cekap menggunakan pendekatan berasaskan untuk mengesan kitaran. Kaedah ini secara dinamik membina graf dan cek untuk tepi berlebihan pada setiap langkah. Penyelesaian ini memastikan ketepatan dengan mematuhi kekangan masalah dan mengeluarkan kelebihan yang membentuk kitaran dan berlaku terakhir dalam input.

Pautan kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberikan repositori bintang di GitHub atau berkongsi jawatan di rangkaian sosial kegemaran anda? Sokongan anda sangat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, jangan ragu untuk mengikuti saya:

• LinkedIn
• github

Atas ialah kandungan terperinci . Sambungan berlebihan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!