Finde den schwersten (heaviest) Knoten in einem Graphen
Gegeben ist ein ungerichteter Graph mit
v Knoten und e Kanten. Du sollst den Knoten mit dem größten „Gewicht“ (gemessen an der Anzahl seiner Verbindungen) ermitteln. Je mehr Nachbarn ein Knoten hat, desto schwerer ist er. Falls es mehrere Knoten mit derselben maximalen Anzahl an Nachbarn gibt, soll der Knoten mit der kleinsten Nummer ausgegeben werden.Eingabe
Die erste Zeile enthält zwei ganze Zahlen
v (1 ≤ v ≤ 1000) und e (1 ≤ e ≤ 100 000).In den folgenden
e Zeilen stehen jeweils zwei ganze Zahlen v1 und v2 (1 ≤ v1, v2 ≤ v). Diese bedeuten, dass der Knoten v1 mit dem Knoten v2 verbunden ist und umgekehrt.Ausgabe
Das Programm soll den kleinsten Index des Knotens mit dem größten Gewicht ausgeben.
Beispiele
Eingabe | Ausgabe |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 2 |
Erläuterung
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB