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 <= n <= 100
• m == tepi.panjang
• 0 <= m <= n * (n - 1) / 2
• tepi[i].panjang == 2
• 0 <= tepi[i][j] <= n - 1
• 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

  
  
  Penjelasan:




Penghuraian Input:



n ialah bilangan pasukan.

tepi ialah senarai tepi terarah dalam graf.



Memulakan Dalam Darjah:


Buat tatasusunan dalam Darjah saiz n yang dimulakan kepada 0.



Kira Dalam Darjah:


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



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.



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




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).



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!