Algorithmes et Structures de Données

Compter le nombre d’étoiles dans un graphe

Étant donné un graphe non orienté avec v sommets et e arêtes, vous devez déterminer combien de graphes en étoile il contient.

Un graphe en étoile est un graphe possédant un sommet central connecté à tous les autres sommets, tandis que ces derniers ne sont connectés qu’au sommet central et à aucun autre sommet.

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

Entrée

La première ligne de l’entrée contient deux entiers v (1 ≤ v ≤ 1000) et e (1 ≤ e ≤ 10 000).

Les e lignes suivantes fournissent des paires d’entiers v1, v2 (1 ≤ v1, v2 ≤ v) qui représentent une arête entre v1 et v2.

Sortie

Le programme doit afficher le nombre de graphes en étoile présents dans le graphe donné.

Exemples

Entrée

Sortie

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