I solved it using binary search.
Firstly I stored all the pairs which were not friends together as a pair in a vector.
Then I checked if both of these person have any common friend , by binary search .
If yes , ans += 2 .
Both of them use BitSet concept. I’ll try and write this in terms for even a layman to understand. If you’re a beginner, i’m assuming you know what the ‘&’ bitwise operator returns for 2 binary values. If you don’t then just google it. It’s pretty easy
C++:
build up the bitset. ‘bitset gr[no. of vertices]’
now run a loop for each vertex. Check for the vertices for this vertex which do not share a common edge (bit will not be set e.i 1 here)
simply put if((i!=j)&&((gr[i]&gr[j]).any()>0)) then ans++; [.any() method checks if the number gr[i]&gr[j] has any bit set as 1. This would obviously physically mean that they share one or more than 1 common edge]
Voila!. Once you’ve interated through all loops, you have your answer.
Same concept. Its gets much easier here.JAVA has an awesome ‘Bitset.intersects(BitSet)’ method. Intersect means that they have atleast one common bit set.
1.Create an ArrayList of Bitsets and build the graph up.
2.Now same. run a loop for each vertex to check for non adjacent vertices. After that, simply check when (i!=j && !gr.get(i).get(j)) → if(gr.get(i).intersects(gr.get(j))), ans++;
CAUTION: the second .get(j) is a bitset method. Not the arrayList one. It checks if the bit is set at position j
consider 1 and 2 to be friend 2 and 3 to be friend and 3 and 4 to be friend then 1 and 4 does not have any mutual friends as friend of 1 is 2 and friend of 4 is 3.
I tried your code for small tricky test cases involving cycles… works good for them.
But when I changed all 1000-values to 2000-values (since n<=2000 and not <=1000), it gets a TLE.
Consider the following example with 5 friends: 1->2, 1->3, 2->4, 3->5. The expected answer is 6, while your algorithm gives 12. a) 2 and 3 are not friends, but they have friend 1 in common. b) 4 and 1 are not friends, but they have friend 2 in common. c) 5 and 1 are not friends, but they have friend 3 in common. The issue with your approach is that you only get the sum of the number of indirectly connected friends in the CC (for every friend), and that doesn’t help us at all to compute the desired answer.