382. Counting Triangles
Edges are undirected again. Print how many triangles the graph contains, meaning how many sets of three vertices where all three pairs are joined.
This is the problem that pays for an adjacency MATRIX. Checking every set of three vertices means asking "is there an edge between a and b" a great many times, and an adjacency list answers that by scanning a list while a matrix answers it by one array lookup.
The trade is memory. The matrix is n by n regardless of how few edges
there are, which is why n is small here and large everywhere else in this
topic.
Count each triangle once by only ever considering a < b < c. Without that,
every triangle is found six times, once per ordering of its three vertices.
Constraints - `1 ≤ n ≤ 200` - `0 ≤ m ≤ 5000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
edges. Each of the next m lines contains two integers u and v, an
undirected edge between those vertices. Vertices are numbered 1 to n.
Output
Print one integer, the number of triangles.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.