PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
MEDIUM
PREREQUISITES:
SQRT DECOMPOSITION
PROBLEM:
Find the number of triangles with pairwise distinct edge colors in a graph.
EXPLANATION:
One way to do it is to divide the vertices into heavy and light. Heavy vertices are vertices with at least \sqrt{2m} neighbours. The rest of the vertices are light.
For each heavy vertex w, we iterate over all possible edges (u, v). Then, we check if (u, v, w) form a colorful triangle. This part takes O(m\sqrt{m}) time.
For each edge with both endpoints light, we iterate through the adjacency list of one of the endpoints u and check if the two endpoints and the vertex from the adjacency list form a colorful triangle. Note that care has to be taken to avoid overcounts (in particular we should ignore heavy vertices, for example). This part works in O(\sqrt{m}) per edge and thus O(m\sqrt{m}).
The complexity is O(m\sqrt{m}).
There seems to be other solutions as well but I will not describe them here.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
