Number Of Triangles In An Undirected Graph

Moderate

0/80

Average time to solve is 10m

Contributed by

5 upvotes

Asked in companies

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 )

Input format :

The very first line contains an integer ‘T’ which denotes the number of test cases.
The first line of each test case contains a single integer ‘V’ denoting the number of vertices of the graph.
The following ‘V’ lines of each test case contain ‘V’ integers representing the edges.
If the integer is 1, then we say that there’s an edge from its row Number to column Number. Here, 0-based indexing has been followed.

Output Format :

For every test case, print the number of triangles in the graph.

##### Note : You don’t need to print anything. It has already been taken care of. Just implement the given function.

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:

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 :

Sample Output 2 :

0
2

Sample Input 1:

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