Überprüfen, ob der Graph bipartit ist
Ein Graph wird als bipartit bezeichnet, wenn er sich mit zwei Farben so einfärben lässt, dass keine zwei benachbarten Knoten die gleiche Farbe tragen.
Die Feststellung, ob ein Graph bipartit ist, kann helfen, bestimmte Strukturen und Eigenschaften zu erkennen. Dies ermöglicht eine effiziente Problemlösung in Bereichen wie Terminplanung, Ressourcenverwaltung und Konfliktlösung. Außerdem erlauben bipartite Graphen oft einfachere Algorithmen und Optimierungen, etwa bei Maximum-Matching-Verfahren oder der Graphfärbung.
Sie erhalten einen ungerichteten Graphen mit
v Knoten und e Kanten. Ihre Aufgabe ist es zu prüfen, ob der Graph bipartit ist oder nicht.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
v (1 ≤ v ≤ 100 000) und e (1 ≤ e ≤ 100 000).In den folgenden
e Zeilen stehen jeweils zwei ganze Zahlen v1 und v2 (1 ≤ v1, v2 ≤ v). Dies bedeutet, dass der Knoten v1 mit dem Knoten v2 und umgekehrt verbunden ist.Ausgabe
Das Programm soll
Yes ausgeben, wenn der Graph bipartit ist, und No, falls dies nicht der Fall ist.Beispiele
Eingabe | Ausgabe |
2 1
2 1 | Yes |
3 2
2 1
1 3 | Yes |
3 3
1 2
1 3
2 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB