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.
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