Compter le nombre de triangles dans un graphe
Étant donné un graphe non orienté avec
v sommets et e arêtes, vous devez déterminer le nombre de triangles présents dans ce graphe.Un triangle dans un graphe est un ensemble de 3 sommets qui sont tous reliés entre eux.
Par exemple, le graphe illustré comporte 3 triangles :
- 1-2-5
- 2-5-4
- 3-2-4
Entrée
La première ligne d'entrée contient deux entiers
v (1 ≤ v ≤ 100) et e (1 ≤ e ≤ ).Les
e lignes suivantes contiennent des paires d'entiers v1, v2 (1 ≤ v1, v2 ≤ v), indiquant que le sommet v1 est relié au sommet v2 et inversement.Sortie
Le programme doit afficher le nombre de triangles dans le graphe donné.
Exemples
Entrée | Sortie |
5 7
1 2
1 5
2 5
4 5
2 4
2 3
3 4 | 3 |
3 2
1 2
2 3 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB