Trouver le Champion II

2924. Trouver Champion II

Difficulté :Moyen

Thèmes : Graphique

Il y a n équipes numérotées de 0 à n - 1 dans un tournoi ; chaque équipe est également un nœud dans un DAG.

Vous recevez l'entier n et un tableau d'entiers 2D indexé 0 de longueur m représentant le DAG, où >dges[i] = [u _i, v_i] indique qu'il y a un avantage dirigé de l'équipe u_i à l'équipe v_i dans le graphique.

Un bord dirigé de a vers b dans le graphique signifie que l'équipe a est plus forte que l'équipe b et que l'équipe b est plus faible que l'équipe a.

L'équipe a sera la championne du tournoi s'il n'y a pas d'équipe b qui est plus forte que l'équipe a.

Renvoyer l'équipe qui sera le champion du tournoi s'il y a un champion unique, sinon, retourner -1.

Remarques

• Un cycle est une série de nœuds a₁, a₂, ..., a_n, a_{n 1} tel que le nœud a₁ est le même nœud que le nœud a_{n 1}, les nœuds a₁, a₂, ..., a_n sont distincts, et il existe un dirigé arête du nœud a_i au nœud a_{i 1} pour chaque i dans la plage [1, n].
• Un DAG est un graphe orienté qui ne possède aucun cycle.

Exemple 1 :

• Entrée : n = 3, bords = [[0,1],[1,2]]
• Sortie : 0
• Explication : L'équipe 1 est plus faible que l'équipe 0. L'équipe 2 est plus faible que l'équipe 1. Le champion est donc l'équipe 0.

Exemple 2 :

• Entrée : n = 4, bords = [[0,2],[1,3],[1,2]]
• Sortie : -1
• Explication : L'équipe 2 est plus faible que l'équipe 0 et l'équipe 1. L'équipe 3 est plus faible que l'équipe 1. Mais l'équipe 1 et l'équipe 0 ne sont pas plus faibles que les autres équipes. La réponse est donc -1.

Contraintes :

• 1 <= n <= 100
• m == bords.longueur
• 0 <= m <= n * (n - 1) / 2
• bords[i].length == 2
• 0 <= bord[i][j] <= n - 1
• bords[i][0] != bords[i][1]
• L'entrée est générée de telle sorte que si l'équipe a est plus forte que l'équipe b, l'équipe b n'est pas plus forte que l'équipe a.
• L'entrée est générée de telle sorte que si l'équipe a est plus forte que l'équipe b et que l'équipe b est plus forte que l'équipe c, alors l'équipe a est plus forte que l'équipe c.

Indice :

1. Le(s) champion(s) doivent avoir un diplôme 0 dans le DAG.

Solution :

Nous devons identifier la ou les équipes avec un en degré de 0 dans le graphique acyclique dirigé (DAG) donné. Les équipes sans avantage entrant représentent des équipes qu'aucune autre équipe n'est plus forte, ce qui en fait des candidats au titre de champion. S’il y a exactement une équipe avec un in-degré de 0, c’est l’unique champion. S'il y a plusieurs ou aucune équipe de ce type, le résultat est -1.

Implémentons cette solution en PHP : 2924. Trouver Champion II

  
  
  Explication:




Analyse des entrées :



n est le nombre d'équipes.

edge est la liste des arêtes dirigées dans le graphique.



Initialiser In-degree :


Créez un tableau enDegré de taille n initialisé à 0.



Calculer le diplôme :


Pour chaque bord [u, v], incrémentez le degré entrant de v (l'équipe v a un bord entrant supplémentaire).



Trouver des candidats :


Parcourez le tableau inDegree et collectez les indices où le degré en est de 0. Ces indices représentent des équipes sans autre équipe plus forte.



Déterminer le champion :


Si exactement une équipe a un degré 0, c'est l'unique champion.
Si plusieurs équipes ou aucune équipe n'a un degré 0, renvoyez -1.





  
  
  Exemple de procédure pas à pas



  
  
  Exemple 1 :



Entrée : n = 3, bords = [[0, 1], [1, 2]]

En degré : [0, 1, 1]

Équipes avec un diplôme 0 : [0]

Sortie : 0 (l'équipe 0 est le champion unique).



  
  
  Exemple 2 :



Entrée : n = 4, bords = [[0, 2], [1, 3], [1, 2]]

En degré : [0, 0, 2, 1]

Équipes avec un degré 0 : [0, 1]

Sortie : -1 (Il existe plusieurs champions potentiels).



  
  
  Analyse de complexité




Complexité temporelle :


Calcul en degrés : O(m), où m est le nombre d'arêtes.
Vérification des équipes : O(n), où n est le nombre d'équipes.
Total : O(n m).



Complexité spatiale :



Tableau inDegree : O(n).




Cette solution est efficace et fonctionne dans les limites données.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!