Finde Champion II

2924. Finde Champion II

Schwierigkeit:Mittel

Themen:Grafik

In einem Turnier gibt es n Teams mit den Nummern 0 bis n - 1; Jedes Team ist auch ein Knoten in einem DAG.

Sie erhalten die Ganzzahl n und ein 0-indiziertes 2D-Integer-Array mit Kanten der Länge m, das den DAG darstellt, wobei >dges[i] = [u _i, v_i] zeigt an, dass es einen gerichteten Vorsprung vom Team gibt u_i zum Team v_i in der Grafik.

Eine gerichtete Kante von a nach b im Diagramm bedeutet, dass Team a stärker als Team b und Team b schwächer als Team a ist.

Team A wird Meister des Turniers, wenn es kein Team B gibt, das stärker ist als Team A.

Geben Sie das Team zurück, das der Champion des Turniers sein wird, wenn es einen einzigartigen Champion gibt, andernfalls geben Sie -1 zurück.

Notizen

• Ein Zyklus ist eine Reihe von Knoten a₁, a₂, ..., a_n, a_{n 1}, so dass Knoten a₁ derselbe Knoten wie Knoten ist a_{n 1}, die Knoten a₁, a₂, ..., a_n sind verschieden, und es gibt eine gerichtete Kante vom Knoten a_i zum Knoten a_{i 1} für jedes i im Bereich [1, n].
• Ein DAG ist ein gerichteter Graph, der keinen Zyklus hat.

Beispiel 1:

• Eingabe: n = 3, Kanten = [[0,1],[1,2]]
• Ausgabe: 0
• Erklärung:Team 1 ist schwächer als Team 0. Team 2 ist schwächer als Team 1. Der Champion ist also Team 0.

Beispiel 2:

• Eingabe: n = 4, Kanten = [[0,2],[1,3],[1,2]]
• Ausgabe: -1
• Erklärung: Team 2 ist schwächer als Team 0 und Team 1. Team 3 ist schwächer als Team 1. Aber Team 1 und Team 0 sind nicht schwächer als alle anderen Teams. Die Antwort lautet also -1.

Einschränkungen:

• 1 <= n <= 100
• m == Kanten.Länge
• 0 <= m <= n * (n - 1) / 2
• edges[i].length == 2
• 0 <= Kante[i][j] <= n - 1
• Kanten[i][0] != Kanten[i][1]
• Die Eingabe wird so generiert, dass Team B nicht stärker ist als Team A, wenn Team A stärker ist als Team B.
• Die Eingabe wird so generiert, dass, wenn Team a stärker ist als Team b und Team b stärker ist als Team c, dann Team a stärker ist als Team c.

Hinweis:

1. Der/die Champion(s) sollten in der DAG den In-Grad 0 haben.

Lösung:

Wir müssen die Teams mit einem In-Grad von 0 im gegebenen gerichteten azyklischen Graphen (DAG) identifizieren. Teams ohne eingehende Vorteile stellen Teams dar, denen kein anderes Team stärker ist, was sie zu Kandidaten für den Titel macht. Wenn es genau ein Team mit einem In-Grad von 0 gibt, ist es der einzigartige Champion. Wenn es mehrere oder keine solchen Teams gibt, ist das Ergebnis -1.

Lassen Sie uns diese Lösung in PHP implementieren: 2924. Finde Champion II

  
  
  Erläuterung:




Eingabeanalyse:



n ist die Anzahl der Teams.

Kanten ist die Liste der gerichteten Kanten im Diagramm.



In-Grad initialisieren:


Erstellen Sie ein Array in Grad der Größe n, initialisiert auf 0.



In-Grad berechnen:


Erhöhen Sie für jede Kante [u, v] den In-Grad von v (Team v hat eine weitere eingehende Kante).



Kandidaten finden:


Durchlaufen Sie das inDegree-Array und sammeln Sie Indizes, bei denen der In-Grad 0 ist. Diese Indizes repräsentieren Teams ohne andere stärkere Teams.



Champion bestimmen:


Wenn genau ein Team den In-Grad 0 hat, ist es der einzigartige Champion.
Wenn mehrere Teams oder kein Team den In-Grad 0 haben, geben Sie -1 zurück.





  
  
  Beispiel-Komplettlösung



  
  
  Beispiel 1:



Eingabe: n = 3, Kanten = [[0, 1], [1, 2]]

In-Grad: [0, 1, 1]

Teams mit Abschluss 0: [0]

Ausgabe: 0 (Team 0 ist der einzigartige Champion).



  
  
  Beispiel 2:



Eingabe: n = 4, Kanten = [[0, 2], [1, 3], [1, 2]]

In-Grad: [0, 0, 2, 1]

Teams mit Abschluss 0: [0, 1]

Ausgabe: -1 (Es gibt mehrere potenzielle Champions).



  
  
  Komplexitätsanalyse




Zeitkomplexität:


In-Grade berechnen: O(m), wobei m die Anzahl der Kanten ist.
Teams prüfen: O(n), wobei n die Anzahl der Teams ist.
Gesamt: O(n m).



Weltraumkomplexität:



inDegree-Array: O(n).




Diese Lösung ist effizient und funktioniert innerhalb der gegebenen Einschränkungen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonFinde Champion II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!