Cari Juara II

2924. Cari Juara II

Kesukaran: Sederhana

Topik: Graf

Terdapat n pasukan bernombor dari 0 hingga n - 1 dalam kejohanan; setiap pasukan juga merupakan nod dalam DAG.

Anda diberi integer n dan 0-diindeks tepi tatasusunan integer 2D dengan panjang m mewakili DAG, dengan >dges[i] = [u _i, v_i] menunjukkan bahawa terdapat kelebihan terarah daripada pasukan u_i kepada pasukan v_i dalam graf.

Tepi terarah dari a ke b dalam graf bermakna pasukan a lebih kuat daripada pasukan b dan pasukan b lebih lemah daripada pasukan a.

Pasukan a akan menjadi juara kejohanan jika tiada pasukan b yang lebih kuat daripada pasukan a.

Kembali pasukan yang akan menjadi juara kejohanan jika ada juara unik, jika tidak, pulangkan -1.

Nota

• A kitaran ialah satu siri nod a₁, a₂, ..., a_n, a_{n 1} supaya nod a₁ ialah nod yang sama dengan nod a_{n 1}, nod a₁, a₂, ..., a_n adalah berbeza dan terdapat diarahkan tepi daripada nod a_i ke nod a_{i 1} untuk setiap i dalam julat [1, n].
• A DAG ialah graf terarah yang tidak mempunyai sebarang kitaran.

Contoh 1:

• Input: n = 3, tepi = [[0,1],[1,2]]
• Output: 0
• Penjelasan: Pasukan 1 lebih lemah daripada pasukan 0. Pasukan 2 lebih lemah daripada pasukan 1. Jadi juara adalah pasukan 0.

Contoh 2:

• Input: n = 4, tepi = [[0,2],[1,3],[1,2]]
• Output: -1
• Penjelasan: Pasukan 2 lebih lemah daripada pasukan 0 dan pasukan 1. Pasukan 3 lebih lemah daripada pasukan 1. Tetapi pasukan 1 dan pasukan 0 tidak lebih lemah daripada pasukan lain. Jadi jawapannya ialah -1.

Kekangan:

• 1
• m == tepi.panjang
• 0
• tepi[i].panjang == 2
• 0
• tepi[i][0] != tepi[i][1]
• Input dijana supaya jika pasukan a lebih kuat daripada pasukan b, pasukan b tidak lebih kuat daripada pasukan a.
• Input dijana supaya jika pasukan a lebih kuat daripada pasukan b dan pasukan b lebih kuat daripada pasukan c, maka pasukan a lebih kuat daripada pasukan c.

Petunjuk:

1. Juara sepatutnya mendapat darjah 0 dalam DAG.

Penyelesaian:

Kami perlu mengenal pasti pasukan dengan darjah 0 dalam Graf Akiklik Berarah (DAG) yang diberikan. Pasukan tanpa kelebihan masuk mewakili pasukan yang tiada pasukan lain lebih kuat daripadanya, menjadikan mereka calon untuk menjadi juara. Sekiranya terdapat satu pasukan dengan darjah 0, ia adalah juara yang unik. Jika terdapat berbilang atau tiada pasukan sedemikian, keputusannya ialah -1.

Mari laksanakan penyelesaian ini dalam PHP: 2924. Cari Juara II

<?php /**
 * @param Integer $n
 * @param Integer[][] $edges
 * @return Integer
 */
function findChampion($n, $edges) {
    // Initialize in-degrees for all teams
    $inDegree = array_fill(0, $n, 0);

    // Calculate the in-degree for each team
    foreach ($edges as $edge) {
        $inDegree[$edge[1]]++;
    }

    // Find teams with in-degree 0
    $candidates = [];
    for ($i = 0; $i < $n; $i++) {
        if ($inDegree[$i] == 0) {
            $candidates[] = $i;
        }
    }

    // If exactly one team has in-degree 0, return it; otherwise, return -1
    return count($candidates) === 1 ? $candidates[0] : -1;
}

// Example 1
$n1 = 3;
$edges1 = [[0, 1], [1, 2]];
echo "Example 1 Output: " . findChampion($n1, $edges1) . PHP_EOL; // Output: 0

// Example 2
$n2 = 4;
$edges2 = [[0, 2], [1, 3], [1, 2]];
echo "Example 2 Output: " . findChampion($n2, $edges2) . PHP_EOL; // Output: -1
?>

Penjelasan:

1. Penghuraian Input:

   • n ialah bilangan pasukan.
   • tepi ialah senarai tepi terarah dalam graf.

2. Memulakan Dalam Darjah:

   • Buat tatasusunan dalam Darjah saiz n yang dimulakan kepada 0.

3. Kira Dalam Darjah:

   • Untuk setiap tepi [u, v], naikkan dalam darjah v (pasukan v mempunyai satu lagi kelebihan masuk).

4. Cari Calon:

   • Lelar melalui tatasusunan inDegree dan kumpulkan indeks di mana dalam darjah ialah 0. Indeks ini mewakili pasukan tanpa pasukan lain yang lebih kuat.

5. Tentukan Johan:

   • Jika betul-betul satu pasukan mempunyai darjah 0, ia adalah juara yang unik.
   • Jika beberapa pasukan atau tiada pasukan mempunyai darjah 0, kembalikan -1.

Contoh Panduan

Contoh 1:

• Input: n = 3, tepi = [[0, 1], [1, 2]]
• Dalam ijazah: [0, 1, 1]
• Pasukan dengan dalam darjah 0: [0]
• Output: 0 (Pasukan 0 ialah juara unik).

Contoh 2:

• Input: n = 4, tepi = [[0, 2], [1, 3], [1, 2]]
• Dalam ijazah: [0, 0, 2, 1]
• Pasukan dengan dalam darjah 0: [0, 1]
• Output: -1 (Terdapat berbilang juara berpotensi).

Analisis Kerumitan

1. Kerumitan Masa:

   • Pengiraan dalam darjah: O(m), dengan m ialah bilangan tepi.
   • Memeriksa pasukan: O(n), dengan n ialah bilangan pasukan.
   • Jumlah: O(n m).

2. Kerumitan Angkasa:

   • tatasusunan inDegree: O(n).

Penyelesaian ini cekap dan berfungsi dalam kekangan yang diberikan.

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