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...
Top Accenture Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Top HR questions asked in Accenture Software Developer Intern
>
Accenture Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
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
Get AmbitionBox app