Last Updated: 2 Mar, 2021

Number Of Triangles In Directed And Undirected Graphs

Moderate

Asked in companies

Solve now

Problem statement

Ninja has been given two Graphs: a directed graph ‘DIRGRAPH’ and an undirected graph ‘UNDIRGRAPH’. Ninja has to count the number of triangles in each of the graphs.

Can you help Ninja with finding the number of triangles in ‘DIRGRAPH’ and ‘UNDIRGRAPH’.

For Example :

graph1

In this example, this graph is directed and there are two triangles possible.
Triangle 1 : (0 3 2)
Triangle 2 : (0 1 2)

graph1

In this example, this graph is undirected and there are two triangles possible.
Triangle 1 : (0 3 2)
Triangle 2 : (0 1 2)

Input Format :

The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two space-separated integers ‘V1’ and ‘E1’, which represents the number of vertices present in ‘DIR_GRAPH’ and the number of edges present in  ‘DIR_GRAPH’.

The next ‘E1’ lines of each test case contain two single space-separated integers, that denote that there exists an edge between vertex a1 and b1.

The next lines of each test case contain two space-separated integers ‘V2’ and ‘E2’, which represent the number of vertices present in ‘UNDIR_GRAPH’ and the number of edges present in  ‘UNDIR_GRAPH’.

The next ‘E2’ lines of each test case contain two single space-separated integers, that denote that there exists an edge between vertex a2 and b2.

Output Format :

For each test case, print the number of triangles in ‘DIR_GRAPH’ and ‘UNDIR_GRAPH’.

Print the output of each test case in a separate line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 100
2 <= ‘V1’,’V2’ <= 1000
1 <= ’E1’ <=  (V1 * (V1 - 1)) / 2
1 <= ’E2’ <=  (V2 * (V2 - 1)) / 2
0 <= ‘a1’, ‘b1’ <= ‘V1’ - 1
0 <= ‘a2’, ‘b2’ <= ‘V2’ - 1

Time Limit: 1 sec

Solve now

Approaches

01 Approach

First, we run three nested loops to find all the triplets ‘VER1’, ‘VER2’, and ‘VER3’ where VER1’, ‘VER2’, and ‘VER3’ represents our first, second, and third vertices of the given graph.

The ‘UNDIR_GRAPH’ triplets ‘VER1’, ‘VER2’, and ‘VER3’ can be permuted to give six combinations. So we divide the total ‘COUNT_TRIANGLE_In_UNDIR_GRAPH’ by 6 to get the actual numbers of triangles.

For example :

If ‘VER1’ = 1

‘VER2’ = 2

‘VER3’ = 3.

Then all possible permutations are { (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1),(3, 1, 2), (3, 2, 1) }.

The ‘DIR_GRAPH’ triplets ‘VER1’, ‘VER2’, and ‘VER3’ can be permuted to give three combinations because, in a directed graph, the order of vertices is essential. So we divide the total ‘COUNT_TRIANGLE_In_DIR_GRAPH’ by 3 to get the actual numbers of triangles.

For example:

If ‘VER1’ = 1

‘VER2’ = 2

‘VER3’ = 3.

Then all possible permutations are { (1, 2, 3), (2, 3, 1), (3, 1, 2) }

Algorithm:

We declare two variables ‘COUNT_TRIANGLE_In_DIR_GRAPH’ and ‘COUNT_TRIANGLE_In_UNDIR_GRAPH’ in which we store the number of triangles in ‘DIR_GRAPH’ and ‘UNDIR_GRAPH’ respectively.
We make an adjacency 2-D matrix ‘ADJ_MAT_DIR_GRAPH’ for ‘DIR_GRAPH’.
We make an adjacency 2-D matrix ‘ADJ_MAT_UNDIR_GRAPH’ for ‘UNDIR_GRAPH’.
We run a loop for ‘i’ = 0 to ‘V1’
- We run a loop for ‘j’ = 0 to ‘V1’
  - We run a loop ‘k’ = 0 to ‘V1’
  - If ADJ_MAT_DIR_GRAPH[i][j] == 1 and ADJ_MAT_DIR_GRAPH[j][k] == 1 and ADJ_MAT_DIR_GRAPH[k][i] == 1
    - ‘COUNT_TRIANGLE_In_DIR_GRAPH’++.
We run a loop for ‘i’ = 0 to ‘V2’
- We run a loop for ‘j’ = 0 to ‘V2’
  - We run a loop ‘k’ = 0 to ‘V2’
  - If ADJ_MAT_UNDIR_GRAPH[i][j] == 1 and ADJ_MAT_UNDIR_GRAPH[j][k] == 1 and ADJ_MAT_UNDIR_GRAPH[k][i] == 1
    - ‘COUNT_TRIANGLE_In_UNDIR_GRAPH’++.
Finally, return ‘COUNT_TRIANGLE_In_DIR_GRAPH’ / 3 and ‘COUNT_TRIANGLE_In_UNDIR_GRAPH’ / 6.

Solve now