Isolierte Knoten in einem Graphen finden
Ein Knoten in einem Graphen wird als isoliert bezeichnet, wenn er über keine Kanten verfügt.
Gegeben ist ein ungerichteter Graph mit
v Knoten und e Kanten. Für jeden Knoten soll ermittelt werden, ob er isoliert ist.Im dargestellten Beispiel ist Knoten 5 isoliert, während alle anderen Knoten Nachbarn haben und daher nicht isoliert sind.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
v (1 ≤ v ≤ 100 000) und e (1 ≤ e ≤ 100 000).Die nächsten
e Zeilen enthalten jeweils ein Paar ganzer Zahlen v1, v2 (1 ≤ v1, v2 ≤ v). Dies bedeutet, dass der Knoten v1 mit dem Knoten v2 verbunden ist und umgekehrt.Ausgabe
Das Programm soll
v Zeilen ausgeben. In jeder Zeile steht „Yes“, wenn der entsprechende Knoten isoliert ist, und „No“, wenn er es nicht ist. Die Knoten sind von 1 bis v durchnummeriert.Beispiele
Eingabe | Ausgabe |
3 2
1 2
2 3
| No
No
No |
7 5
1 7
1 2
7 2
2 3
6 4 | No
No
No
No
Yes
No
No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB