Count the groups of three vertices in a graph that are all joined to each other.
What to build
A triangle counter that relies on fast edge checks.
Requirements
- A triangle is three different vertices with an edge between each pair.
- Count each triangle once, whatever order its vertices are listed in.
- Print the number of triangles.
Input
The first line has n and m. Each of the next m lines has an edge u v. No edge is repeated, and no edge joins a vertex to itself.
Output
The number of triangles.
Constraints
1 ≤ n ≤ 30 and 0 ≤ m ≤ 435.
Example
Input:
4 5
0 1
1 2
2 0
2 3
3 0
Output:
2
Why it works
The program asks "is there an edge?" three times for every set of three vertices. An adjacency matrix answers that in O(1), where an adjacency list would have to be walked each time.
Examples
Example 1 · Input
4 5 0 1 1 2 2 0 2 3 3 0
Expected output
2
Example 2 · Input
3 2 0 1 1 2
Expected output
0
Hints
Hint 1
Store the graph in an adjacency matrix, so that checking one edge is a single lookup.
Hint 2
Try every set of three vertices a, b and c with a less than b and b less than c.
Hint 3
The three form a triangle when all three edges between them exist.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int adj[30][30];
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][v] = 1;
adj[v][u] = 1;
}
int count = 0;
for (int a = 0; a < n; a++) {
for (int b = a + 1; b < n; b++) {
for (int c = b + 1; c < n; c++) {
if (adj[a][b] && adj[b][c] && adj[a][c]) count++;
}
}
}
printf("%d\n", count);
return 0;
}