Cari Diameter Minimum Selepas Mencantum Dua Pokok

3203. Cari Diameter Minimum Selepas Mencantum Dua Pokok

Kesukaran: Sukar

Topik: Pokok, Depth-First Search, Breadth-First Search, Graph

Terdapat dua pokok tidak berarah dengan nod n dan m, masing-masing bernombor dari 0 hingga n - 1 dan dari 0 hingga m - 1. Anda diberi dua tatasusunan integer 2D masing-masing tepi1 dan tepi2 panjang n - 1 dan m - 1, di mana edges1[i] = [a_i, b_i] menunjukkan bahawa terdapat ialah tepi antara nod a_i dan b_i dalam pokok pertama dan tepi2[i] = [u_i, v_i] menunjukkan bahawa terdapat tepi antara nod u_i dan v _i dalam pokok kedua.

Anda mesti menyambungkan satu nod daripada pokok pertama dengan satu lagi nod daripada pokok kedua dengan tepi.

Kembali minimum yang mungkin diameter pokok yang terhasil.

diameter pokok ialah panjang laluan terpanjang antara mana-mana dua nod dalam pokok itu.

Contoh 1:

• Input: tepi1 = [[0,1],[0,2],[0,3]], tepi2 = [[0,1]]
• Output: 3
• Penjelasan: Kita boleh mendapatkan pokok berdiameter 3 dengan menyambungkan nod 0 daripada pokok pertama dengan mana-mana nod daripada pokok kedua.

Contoh 2:

• Input: tepi1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2, 7]], tepi2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]
• Output: 5
• Penjelasan: Kita boleh mendapatkan pokok berdiameter 5 dengan menyambungkan nod 0 daripada pokok pertama dengan nod 0 daripada pokok kedua.

Kekangan:

• 1 5
• tepi1.panjang == n - 1
• tepi2.panjang == m - 1
• tepi1[i].panjang == tepi2[i].panjang == 2
• tepi1[i] = [a_i, b_i]
• 0 i, b_i
• tepi2[i] = [u_i, v_i]
• 0 i, v_i
• Input dijana supaya tepi1 dan tepi2 mewakili pokok yang sah.

Petunjuk:

1. Andaikan kita menyambungkan nod a dalam tree1 dengan nod b dalam tree2. Panjang diameter pokok yang terhasil akan menjadi yang terbesar daripada 3 nilai berikut:
   1. Diameter pokok 1.
   2. Diameter pokok 2.
   3. Panjang laluan terpanjang yang bermula pada nod a dan sepenuhnya dalam Pokok 1 Panjang laluan terpanjang yang bermula pada nod b dan sepenuhnya dalam Pokok 2 1.
   4. Tambahan dalam nilai ketiga adalah disebabkan oleh kelebihan tambahan yang telah kami tambahkan di antara pokok 1 dan 2.
2. Nilai 1 dan 2 adalah tetap tanpa mengira pilihan a dan b kami. Oleh itu, kita perlu memilih a dan b dengan cara yang meminimumkan nilai 3.
3. Jika kita memilih a dan b secara optimum, ia akan berada dalam diameter Pokok 1 dan Pokok 2, masing-masing. Nod diameter manakah yang harus kita pilih?
4. a ialah pusat diameter pokok 1, dan b ialah pusat diameter pokok 2.

Penyelesaian:

Kita perlu mendekatinya selangkah demi selangkah dengan fokus pada pemahaman cara mengira diameter pokok dan cara penyambungan dua pokok mempengaruhi diameter keseluruhan.

Langkah-langkah untuk menyelesaikan:

1. Cari diameter setiap pokok:

   • Diameter pokok ialah laluan terpanjang antara mana-mana dua nod. Untuk mencarinya, kita boleh menggunakan proses dua langkah berikut:
     1. Lakukan BFS (atau DFS) dari nod sewenang-wenangnya untuk mencari nod paling jauh (mari panggil nod ini A).
     2. Lakukan satu lagi BFS (atau DFS) bermula dari A untuk mencari nod paling jauh dari A (mari kita panggil nod ini B), dan jarak dari A ke B ialah diameter pokok.

2. Tentukan nod optimum untuk disambungkan:

   • Dari petunjuk dalam masalah, cara terbaik untuk meminimumkan diameter tambahan apabila menyambungkan dua pokok adalah dengan menyambungkan pusat diameter kedua-dua pokok. Ini akan meminimumkan laluan terpanjang yang disebabkan oleh tepi baharu.
   • Nod optimum dalam diameter pokok lazimnya ialah "pusat", yang boleh didapati dengan melakukan BFS dari titik akhir diameter dan mencari tengah laluan terpanjang.

3. Meminimumkan jumlah diameter:

   • Setelah kami menemui pusat kedua-dua pokok, diameter baharu ialah maksimum:
     • Diameter Pokok 1.
     • Diameter Pokok 2.
     • Jumlah laluan terpanjang dalam Pokok 1, laluan terpanjang dalam Pokok 2 dan 1 untuk tepi penghubung baharu.

Mari laksanakan penyelesaian ini dalam PHP: 3203. Cari Diameter Minimum Selepas Mencantum Dua Pokok

<?php /**
 * @param Integer[][] $edges1
 * @param Integer[][] $edges2
 * @return Integer
 */
function minimumDiameterAfterMerge($edges1, $edges2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to find the diameter of a tree and the farthest node from a start node
 *
 * @param $n
 * @param $edges
 * @param $start
 * @return array
 */
function bfs($n, $edges, $start) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to find the diameter of a tree and its center
 *
 * @param $n
 * @param $edges
 * @return array
 */
function getDiameterAndCenter($n, $edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$edges1 = [[0,1],[0,2],[0,3]];
$edges2 = [[0,1]];
echo minimumDiameterAfterMerge($edges1, $edges2);  // Output: 3

// Example 2
$edges1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]];
$edges2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]];
echo minimumDiameterAfterMerge($edges1, $edges2);  // Output: 5
?>

Penjelasan:

1. Fungsi Pembantu BFS: Fungsi bfs mengira nod paling jauh daripada nod permulaan yang diberikan dan mengembalikan tatasusunan jarak dan nod paling jauh ditemui. Ini penting untuk mengira diameter pokok.

2. Dapatkan Diameter dan Pusat: Fungsi getDiameterAndCenter mencari diameter pokok dan pusatnya. Bahagian tengah pokok adalah penting untuk meminimumkan diameter pokok baharu apabila menggabungkan dua pokok.

3. Penyelesaian Utama:

   • Kami mula-mula membina senarai bersebelahan untuk kedua-dua pokok.
   • Kami mengira diameter dan pusat untuk kedua-dua pokok.
   • Kami melakukan BFS dari pusat kedua-dua pokok untuk mendapatkan laluan terpanjang dalam setiap pokok.
   • Akhir sekali, kami mengira maksimum tiga nilai untuk mendapatkan diameter minimum pokok yang digabungkan.

Kerumitan Masa:

• Membina senarai bersebelahan: O(n m)
• Perjalanan BFS: O(n m)
• Kerumitan masa keseluruhan ialah O(n m), yang cekap untuk had saiz input 10⁵.

Pendekatan ini memastikan kami mencari diameter minimum yang mungkin apabila menggabungkan kedua-dua pokok.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Cari Diameter Minimum Selepas Mencantum Dua Pokok. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!