Number of Triangles in an Undirected Graph

Determine how many triangles exist in an undirected graph. A triangle is defined as a cyclic path of length three that begins and ends at the same vertex.

Input:

The first line contains an integer 'T', the number of test cases. For each test case: The first line has a single integer 'V', representing the number of vertices in the graph. The next 'V' lines contain 'V' integers that represent the adjacency matrix of the graph, where '1' indicates an edge, and '0' indicates no edge. The graph uses 0-based indexing.

Output:

For each test case, output the number of triangles present in the graph.

Example:

Input:
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
Output:
0 2
Explanation:

For the first test case, there are no triangular cycles. For the second test case, two triangles exist: 0-1-2 and 1-2-3.

Constraints:

  • 1 <= T <= 5
  • 1 <= V <= 102
  • 0 <= V[i][j] <= 1

Where 'i' and 'j' are the row and column indices, respectively. If V[i][j] = 1, there is an edge from 'i' to 'j'.

Time Limit: 1 second.

Note:

You do not need to print anything; focus on implementing the function to solve the problem.

AnswerBot
2d

Count the number of triangles in an undirected graph.

  • Iterate through all possible triplets of vertices to check for triangles.

  • Use the adjacency matrix to determine if there is an edge between vertices...read more

Help your peers!
Add answer anonymously...
Accenture Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter