Number of triplets with same edge color in complete graph

Question

I'm practicing for National programming competition and I came on this problem:

We are given undirected complete graph with N vertices. Every edge in graph has color red or green. We should find number of triplets(i,j,k) of vertices such that edges(i,j),(j,k)and(i,k) all have same color. We are given N and M where M is number of red colored edges in graph. And in next M lines we are given all red edges that exist in this graph. Rest of the edges(edges that are not in the input are green). N is between 3 and 300000 (3<=N<=300000) M is between 1 and 300000 (1<=M<=300000) Time limit is 2s I'm guessing that solution should have O(NlogN) complexity but I don't have idea how to solve it in that complexity.

Can someone please give me some idea on how to approach and solve this problem?

Thanks in advance.

Answer 1

It's enough to count the red degree and green degree of every vertex, then do some arithmetic.

First let's count the number of monochromatic paths of length $2$: pairs of edges $(i,j)$ and $(j,k)$ of the same color. For each vertex $j$, if it has $r_j$ red edges and $g_j$ green edges, there are $\binom{r_j}{2}$ red paths and $\binom{g_j}{2}$ blue paths that have $j$ as their middle vertex. This can be computed and added up quickly for all $j$ - you should be able to do it in $O(M+N)$ time.

Let's suppose that we've counted $P$ such paths.

There are $\binom N3$ triangles total. A monochromatic triangle contains $3$ monochromatic paths, but a mixed triangle still contains $1$ monochromatic path. So if $X$ is the unknown number of monochromatic triangles, then $$ P = 3 \cdot X + 1 \cdot \left(\binom N3 - X\right) = \binom N3 + 2X \implies X = \frac12\left(P - \binom N3\right). $$

Answer 2

Let $A$ be the adjacency matrix for the red edges, and $B$ the adjacency matrix for the green edges. Thus $A+B = C$ which has all its off-diagonal elements $1$ and diagonal elements $0$. The number of monochromatic triangles is $$\frac{1}{6} \text{Tr}(A^3 + B^3) = \frac{1}{6} \text{Tr}(A^3 + (C-A)^3) = \frac{1}{6}\text{Tr}(C^3) - \frac{1}{2} \text{Tr}(AC^2) + \frac{1}{2} \text{Tr}(A^2C) $$ Now $$\eqalign{\text{Tr}(C^3) &= N(N-1)(N-2)\cr \text{Tr}(AC^2) &= 2(N-2) M\cr \text{Tr}(A^2C) &= \sum_{i=1}^N \deg(i)(\deg(i)-1)}$$ where $\deg(i)$ is the degree of vertex $i$ in the red graph, i.e. the number of red edges incident on vertex $i$. Thus all you need besides $N$ and $M$ are the degrees of the vertices.