# Number Of Triangles In An Undirected Graph

Moderate
0/80
Average time to solve is 10m
Contributed by

## Problem statement

Given an undirected graph, find how many triangles it can have where a triangle is a cyclic path of length three which begins and end at the same vertex.

#### An undirected graph is a graph in which if you can go from a vertex, say, ‘A’ to ‘B,’ you can come back to ‘A’ from ‘B.’

For example:

``````In this graph, we can visit from vertex 1 to 2, then we can also visit from vertex 2 to 1. This is true for all vertices.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 5
1 <= V <= 10^2
0 <= V[i][j] <= 1

Where ‘i’ and ‘j’s are the row number and column number, respectively, if V[i][j] = 1, it means there’s an edge from ‘i’ to ‘j’s; otherwise, there’s no edge.

Time Limit: 1 sec
``````
Sample Input 1:
``````2
2
0 1
1 0
5
0 1 1 0 1
1 0 1 1 0
1 1 0 1 0
0 1 1 0 1
1 0 0 1 0
``````
Sample Output 1:
``````0
2
``````

Explanation for Sample Output 1 :

``````In the first test case, the edges are as follows :

0 --- 1

As we can see, there are no cycles with three vertices. Hence the output is 0.

In the second case, the edges are as follow :

The two cycles are :
0 - 1 - 2
1 - 2 - 3

Note: there are other cycles as well (0-1-2-3-4),(0-1-3-4) however we are considering only those cycles, where the number of vertices is 3
``````
Sample Input 2 :
``````2
3
0 1 1
1 0 0
1 0 0
4
0 0 1 1
0 0 1 1
1 1 0 1
1 1 1 0
``````
Sample Output 2 :
``````0
2
``````
##### Sample Input 1:
``````2
2
0 1
1 0
5
0 1 1 0 1
1 0 1 1 0
1 1 0 1 0
0 1 1 0 1
1 0 0 1 0
``````
##### Sample Output 1:
``````0
2
``````

#### Explanation for Sample Output 1 :

``````In the first test case, the edges are as follows :

0 --- 1

As we can see, there are no cycles with three vertices.
Hence the output is 0.

In the second case, the edges are as follow :
``````

``````The two cycles are :
0 - 1 - 2
1 - 2 - 3

Note: there are other cycles as well (0-1-2-3-4),(0-1-3-4) however we are considering only those cycles, where the number of vertices is 3
``````
Console