Anzahl der Sterne in einem Graphen zählen
Gegeben ist ein ungerichteter Graph mit
v Knoten und e Kanten. Gesucht ist die Anzahl der Stern-Graphen (star graphs), die in diesem Graphen enthalten sind.Ein Stern-Graph ist ein Graph mit einem zentralen Knoten, der mit allen anderen Knoten verbunden ist. Alle übrigen Knoten sind nur mit diesem zentralen Knoten und nicht untereinander verbunden.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
v (1 ≤ v ≤ 1000) und e (1 ≤ e ≤ 10 000).Die folgenden
e Zeilen enthalten jeweils ein Paar ganzer Zahlen v1, v2 (1 ≤ v1, v2 ≤ v), das eine Kante zwischen v1 und v2 beschreibt.Ausgabe
Das Programm soll die Anzahl der Stern-Graphen im gegebenen Graphen ausgeben.
Beispiele
Eingabe | Ausgabe |
7 6
1 5
2 5
3 5
7 5
6 5
4 5 | 1 |
8 7
1 5
2 5
3 5
7 5
6 5
4 5
1 8 | 0 |
8 6
1 2
2 3
4 2
5 6
7 6
8 6 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB