In this HackerEarth Counting triplets problem solution You are given an undirected, complete graph G that contains N vertices. Each edge is colored in either white or black. You are required to determine the number of triplets (i,j,k) (1 <= i < j < k <= N) of vertices such that the edges (i,j), (j,k), (i,k) are of the same color.

There are M white edges and N(N - 1)/ 2 - M black edges.


HackerEarth Counting triplets problem solution


HackerEarth Counting triplets problem solution.

import numpy as np
n,m=map(int,input().split())
edge={}
deg=np.zeros(n).astype(np.int)
#assert n<=2000,exit(1)
for i in range(m):
a,b=map(int,input().split())
assert a!=b,exit(1)
assert max(a,b)<=n and min(a,b)>=1, exit(1)
if a>b:
a,b=b,a
if (a,b) in edge:
exit(1)
edge[(a,b)]=True
deg[a-1]+=1
deg[b-1]+=1
ans=0
for i in range(n):
ans+=deg[i]*(n-deg[i]-1)
#print(ans)
ALL=n*(n-1)*(n-2)/6
ALL-=ans/2
print(int(ALL))

Second solution

n,m = map(int,input().split())
d = [0] * (n + 5)
for i in range(m):
x,y = map(int,input().split())
d[x] += 1
d[y] += 1
ans = 0
for i in range(1,n + 1):
ans += d[i] * (n - 1 - d[i])
print((n * (n - 1) * (n - 2) // 3 - ans) // 2)