In vivek and birthday problem

#1

in this problem we just have to count no of vertives which has incoming edges , then why is giving wrong ans in 2 test case ?

#2

Counting incoming edges will not give you correct answer.
Think if we have 5 vertices and have two sets one contains {1,2,3} and other contains {4,5}.
Let suppose set1 forms a cycle i,e 1->2 , 2->3 , 3->1 and set 2 is disjoint fromt set1

Example
5 4
1 2
2 3
3 1
4 5

So in this case he will not invite 1,2,3 and only invite 5 , ans will be 1.
And from your logic ,your ans will be 4.

#3

hi thanks for reply , i am just confused with the term dependent , like in your example given 4 is dependent on 5 , so is we have to take both 4 and 5 , or we just have to take 5 because of dependency and we can ignore 4 ???

#4

Sry my mistake, ans will be 1. We will only call 5 as if we call 4 then it is definitely sure that 5 is also invited as 4 is dependent on 5. 4 will only come if 5 is invited.

#5

it seems in your previous comment that we have to fing minimum connected component , i typed the code and submitted and got passed all cases . https://ide.codingblocks.com/s/125413 , not you are telling again what i am telling previously , please clear it out , what i will supposed to do ???

#6

You passed test cases but your code does not cover corner test cases.

5 6
1 2
2 4
4 3
3 2
5 1
5 4

Output should be 3 , we will invite 2 and 2 is dependent on 4 that means 4 is also invited and 4 is dependent on 3 that means 3 is also invited , and 3 is dependent on 2 , which we have already invited,
So invitation gave to 3 friends only {2,4,3}.
but your code gave 1.

Let me tell you more precisely so that you understand it.

For each pair p(a,b), we add a connection from a to b i.e. we insert ‘b’ to the node[a]. Thus if ‘a’ is selected ‘b’ would automatically be selected.
Now we take each node[i] and traverse through the connections till all the leaf nodes and count the total nodes directly/indirectly connected to that particular node[i].
We find that node[i] which has the minimum number of connections.

#7

oh yes, it can we easily done with dfs , thanks