. Cari negeri selamat akhirnya

802. Cari Keadaan Selamat Akhirnya

Kesukaran: Sederhana

Topik: Carian Pertama Kedalaman, Carian Luas-Pertama, Graf, Isih Topologi

Terdapat graf terarah bagi n nod dengan setiap nod dilabelkan dari 0 hingga n - 1. Graf diwakili oleh 0-diindeks graf tatasusunan integer 2D dengan graf[i] ialah tatasusunan integer daripada nod bersebelahan dengan nod i, bermakna terdapat tepi dari nod i ke setiap nod dalam graf[i].

Nod ialah nod terminal jika tiada tepi keluar. Nod ialah nod selamat jika setiap laluan yang mungkin bermula dari nod itu menuju ke nod terminal (atau nod selamat yang lain).

Kembalikan tatasusunan yang mengandungi semua nod selamat graf. Jawapan hendaklah disusun mengikut urutan menaik.

Contoh 1:

• Input: graf = [[1,2],[2,3],[5],[0],[5],[],[]]
• Output: [2,4,5,6]
• Penjelasan: Graf yang diberikan ditunjukkan di atas. Nod 5 dan 6 ialah nod terminal kerana tiada tepi keluar daripada salah satu daripadanya. Setiap laluan bermula pada nod 2, 4, 5 dan 6 semuanya menuju ke nod 5 atau 6.

Contoh 2:

• Input: graf = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
• Output: [4]
• Penjelasan: Hanya nod 4 ialah nod terminal dan setiap laluan bermula pada nod 4 menuju ke nod 4.

Kekangan:

• n == graf.panjang
• 1 4
• 0
• 0
• graf[i] diisih dalam susunan yang semakin meningkat.
• Graf mungkin mengandungi gelung kendiri.
• Bilangan tepi dalam graf akan berada dalam julat [1, 4 * 10⁴].

Penyelesaian:

Kami perlu mengenal pasti semua nod selamat dalam graf. Ini melibatkan pemeriksaan jika bermula dari nod tertentu, setiap laluan akhirnya mencapai nod terminal atau nod selamat yang lain. Penyelesaiannya menggunakan Depth-First Search (DFS) untuk mengesan kitaran dan mengklasifikasikan nod sebagai selamat atau tidak selamat.

Wawasan Utama:

1. nod terminal : nod tanpa tepi keluar adalah nod terminal.
2. nod selamat : Node selamat jika, bermula dari nod itu, semua jalan akhirnya membawa kepada nod terminal atau nod selamat lain.
3. Pengesanan kitaran : Jika nod adalah sebahagian daripada kitaran, ia bukan nod yang selamat kerana laluan bermula daripadanya tidak akan membawa kepada nod terminal.

Pendekatan:

• Kami menggunakan DFS untuk meneroka setiap nod dan menentukan sama ada ia adalah sebahagian daripada kitaran. Nod yang merupakan sebahagian daripada kitaran atau membawa kepada kitaran ditandakan tidak selamat.
• nod yang akhirnya membawa kepada nod terminal atau nod selamat lain ditandakan selamat.

kami menggunakan array yang dikunjungi dengan tiga negeri:

• 0: Node belum dikunjungi.
• 1: Node sedang dikunjungi (iaitu, dalam timbunan rekursi).
• 2: Nod telah diproses sepenuhnya dan selamat.

Langkah:

1. melakukan DFS untuk setiap nod.
2. Gunakan negeri -negeri yang dikunjungi untuk menandakan nod selamat/tidak selamat.
3. Kumpulkan semua nod yang selamat.

mari kita melaksanakan penyelesaian ini dalam php: 802. Cari negeri selamat akhirnya

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

/**
 * DFS helper function
 *
 * @param $node
 * @param $graph
 * @param $visited
 * @return int|mixed
 */
function dfs($node, $graph, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];

print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
?>

Penjelasan:

1. fungsi DFS :

   • Fungsi DFS melakukan carian mendalam pada nod, menandakannya sebagai "melawat" (1) apabila ia bermula dan "selamat" (2) apabila semua jirannya selamat.
   Jika mana -mana jirannya membawa kepada kitaran (ditunjukkan oleh DFS ($ jiran) == 1), nod ditandakan tidak selamat (1).
   Jika semua jiran membawa kepada nod terminal atau nod selamat, ia ditandakan sebagai selamat (2).

2. Fungsi utama :

   kita meleleh melalui semua nod dan gunakan DFS untuk memeriksa sama ada setiap nod selamat atau tidak.
   semua nod selamat dikumpulkan dalam array $ Safenodes dan dikembalikan.

Contoh Walkthrough:

Contoh 1:

$graph = [[1,2],[2,3],[5],[0],[5],[],[]];
print_r(eventualSafeNodes($graph));

Dalam contoh ini, nod 5 dan 6 adalah nod terminal (tiada tepi keluar).
node 4 membawa kepada nod 5, jadi ia juga selamat.
nod 2 membawa kepada nod 5, jadi selamat.
nod 1 dan 0 akhirnya membawa kepada kitaran atau nod yang tidak selamat, jadi mereka tidak selamat.

output:

[2, 4, 5, 6]

Contoh 2:

$graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]];
print_r(eventualSafeNodes($graph));

Dalam contoh ini, hanya node 4 adalah nod terminal, dan semua laluan bermula dari nod 4 membawa kepada nod 4.
semua nod lain akhirnya membawa kepada kitaran atau nod yang tidak selamat.

output:

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

/**
 * DFS helper function
 *
 * @param $node
 * @param $graph
 * @param $visited
 * @return int|mixed
 */
function dfs($node, $graph, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];

print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
?>

Kerumitan Masa dan Ruang:

• Kerumitan Masa: O(n e), dengan n ialah bilangan nod dan e ialah bilangan tepi. Kami melawati setiap nod sekali dan memproses setiap tepi sekali.
• Kerumitan Angkasa: O(n) untuk tatasusunan yang dilawati dan timbunan ulangan.

Penyelesaian ini dengan cekap menentukan nod selamat menggunakan DFS, memastikan kekangan masalah dipenuhi.

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 negeri selamat akhirnya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!