Triangles of imports
Package A imports B and C, and B also imports C: in the import graph, if the directions are forgotten, this is a triangle. How many triangles are there in an undirected graph? Loops do not count, and repeated edges are one edge.
The second test is the 379 packages of the Go standard library and their imports, the third the JavaScript modules of this site, the fourth the streets of central Almaty. After them come graphs where one node is connected to all the others: this happens when all the code imports one library.
Input
The first line holds n and m (1 ≤ n ≤ 2·10⁵, 0 ≤ m ≤ 2·10⁵), then come m edges, pairs of vertex numbers from 0 to n − 1.
Output
The number of triangles.
Examples
Example 1
5 8 0 1 1 2 2 0 2 3 3 0 3 4 1 1 0 1
2
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The simple way is to go over the pairs of neighbours of each vertex. What does this cost for a vertex with a hundred thousand neighbours? How can you make sure no vertex has to go over many neighbours?
2The idea
Direct each edge from the vertex with the smaller degree to the one with the larger (on a tie, from the smaller number). Each triangle gets exactly one vertex from which both its edges go out, the “smallest” of the three, and is found exactly once: for vertex v go over its out-neighbours w, for them their out-neighbours x, and check whether there is an edge v → x.
3Walkthrough
Why is it so fast? No vertex has more than √(2m) outgoing edges. If v has d outgoing ones, all its out-neighbours have degree at least d, and the sum of all degrees is 2m; so d·d ≤ 2m. Going over the pairs “edge v → w and an outgoing edge of w” costs O(m·√m).
The check “is there an edge v → x” is a mark: before working with v, mark all its out-neighbours with the number v, and the check becomes a single array read. This is a case where the choice of graph form solves the problem: lists of outgoing edges plus an array of marks instead of a matrix, for which there would not be enough memory with 2·10⁵ vertices.
3+Solution
4Complexity
O(m·√m) time and O(n + m) memory.
5Common mistakes
- Pairs of neighbours at each vertex. The fifth test is a node with 100,000 neighbours: 5·10⁹ pairs.
- Each triangle three times. Going over without directions finds a triangle from each of its vertices.
- Repeated edges and loops. In the first example the edge 0–1 is written twice, and 1–1 is a loop; there are two triangles there.