Problem

Submissions

Hints & solutions

Discuss

Number Of Triangles In An Undirected Graph

Moderate

0/80

Average time to solve is 10m

Contributed by

6 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

Hint 1

can you think of finding three-pointers i,j,k, such that there is an edge from i to j and j to k and k to j?

Approaches (1)

Approach 1

Brute Force

We call a cycle triangle if its length is 3. So all we need to do is find three vertices such that they all share an edge with each other. In order to find that cycle, we can fix three-pointer ‘i’ , ‘j’ , ‘k’.

If there is an Edge between (i, j), (j, k), and (k, i) then we will add this cycle to our answer.

Algorithm :

Initialize first pointer ‘i’ with 0 value, it will loop till ‘V’ where V is the number of vertices.
Initialize the second pointer ‘j’ with value i+1,
Initialize the third pointer ‘k’ with value j+1
- If there is an edge(i,j) and edge(j,k) and edge(k,i), then
- Increment the answer. Otherwise, continue.

Time Complexity

O(V^3) , Where ‘V’ is the number of vertices.

As there are three nested loop, and each loop is running approximately ‘V’ times; hence complexity is O(V^3)

Space Complexity

O(1)

Matrix space take O(n^2) space

(100% EXP penalty)

Number Of Triangles In An Undirected Graph

Console