Calcolare il numero di triangoli in un grafo
Dato un grafo non orientato con
v vertici e e archi, devi contare il numero di triangoli presenti nel grafo.Un triangolo in un grafo è un insieme di 3 vertici in cui ognuno è collegato a tutti gli altri.
Per esempio, il grafo illustrato presenta 3 triangoli:
- 1-2-5
- 2-5-4
- 3-2-4
Dati in ingresso
La prima riga dell’input contiene due interi
v (1 ≤ v ≤ 100) ed e (1 ≤ e ≤ ).Le successive
e righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v), il che significa che il vertice v1 è connesso al vertice v2 e viceversa.Uscita
Il programma deve stampare il numero di triangoli presenti nel grafo.
Esempi
Ingresso | Uscita |
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