We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
N,P=tuple(map(int,input().strip().split(' ')))sets=[{i}foriinrange(N)]arr=[iforiinrange(N)]#sets[arr[i]] contains iforiinrange(P):a,b=tuple(map(int,input().strip().split(' ')))ifanotinsets[arr[b]]:#union the setsu=sets[arr[a]]|sets[arr[b]]sets[a]=u#store the union at sets[a]forjinu:#pointers to aifj!=a:sets[j]=set()arr[j]=atotal=0non_singles=0foriinrange(N):#print(sets[arr[i]], sets[i])L=len(sets[i])ifL>1:#non-single set with length Lnon_singles+=L#add pairs with first person in the subsettotal+=L*(N-L)#singles = N - non_singles#add pairs with first person in the set of singles total=total+(N-non_singles)*(N-1)#remove double countingtotal=total//2print(total)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Journey to the Moon
You are viewing a single comment's thread. Return to all comments →
I used hash sets and got a simple solution.