Click here to Skip to main content
14,237,088 members
Rate this:
Please Sign up or sign in to vote.
See more:
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

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

Thanks in advance.

What I have tried:

I'm guessing that solution should have O(NlogN) complexity but I don't have idea how to solve it in that complexity.
Posted
Updated 23-Jan-19 5:03am
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100