Algorithmen und Datenstrukturen

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.

profound.academy-graphs-star-graph.drawio.png

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

To check your solution you need to sign in
Sign in to continue