Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1914
Having a simple undirected graph G = (V, E), a triangle is defined as a triple (v1, v2, v3) where v1, v2, v3 ∈ V and (v1, v2) ∈ E for all 1 ≤ i, j ≤ 3 and i ΜΈ= j. In this problem, you are given an undirected graph and asked to count all the triangles in this graph. You are assured that there is no edge in this graph that is the member of more than 2 triangles. Input The first line of input contains an integer T ≤ 250, which is the number of test cases. Each test case begins with a line containing two integers 1 ≤ n ≤ 3000 and m which are the number of vertices and the number of edges in the graph respectively. The next m lines contain two integers 1 ≤ i,j ≤ 3000 indicating that there is an edge between vertex i and vertex j. Tip for C++ Programmers: Any attempt to use ifstream to read the input will exceed the time limit for this problem. Use scanf instead. Output Output for each test case consists of one line containing the number of triangles in the specified graph of the test case.
Sample Input 1 4 6 1 2 2 3 3 1 1 4 2 4 3 4
Sample Output 4
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,n,m,a,b;
cin >> t;
while(t--){
cin >> n >> m;
// need to be in sorted order
map < int,unordered_multiset<int>> graph;
for(int i=0;i < m;i++){
cin >> a >> b;
// single directed edge to prevent duplicates
if(a > b) {
graph[b].insert(a);
} else if(a < b) {
graph[a].insert(b);
}
}
int res = 0;
// foreach vertex v
for(auto v : graph){
// foreach neigh1 of vertex v
for(auto neigh1 : v.second){
// foreach neigh2 of vertex neigh1
for(auto neigh2 : graph[neigh1])
// if v and neigh2 is connected, add one
if(v.second.count(neigh2)> res++;
}
}
cout << res << endl;
}
}
Input
4 6
1 2
2 3
3 1
1 4
2 4
3 4
Output
Demonstration
UVA Online Judge solution - 10973-Triangle Counting - UVA Online Judge solution in C,C++,java