please explain what question is saying ,by providing some another example,different than that is given in example test case.And if we have say 3 friends and only one dependency is there,i.e.,1 will not come if 2 is not invited.Then how many and which friend will come?
Unable to understand the question
Hey @chhabrapiyush480 the question requires you to find the least connected component. So add directed nodes in your graph, and calculate the lengths of all connected components and print the minimum one.
Lets take your example
3 1
1 2
then answer will be 1, because you can either call friend 2 or friend 3.
as you said we have to find minimum length of connected component.But in example you said we can invite 2 or 3,but 1->2 is not a connected component as there is no way to reach 1 from 2?
length of connected component 1->2 is 2 right and for connected component 3 is 1,so we only have 1 choice that is to invite 3 ,help me with this please ,and correct me if i am wrong
But for 2 also it is 1, remember it is a directed graph.
okay i got that we need to find number of vertices reachable from every node in this directed graph,and then need to find the minimum of them.But how to find number of reachable nodes from a node in an efficient way,please provide me some help with this,so that i can do the same without having to do bfs/dfs for every node.
You can run dfs for every node or make a 2-d array for adjacency list of 1000 X 1000. Remember the constraint for N is just 1000, and number of edges is also less than 1000. So the solution is fast enough. Here is the link to working code https://ide.codingblocks.com/s/176381?_ga=2.208200727.400859881.1583502627-1100499067.1583502627
i know that i can use that approach,i just wanted to know a better solution for the same i.e. how to find number of reachable nodes in a directed graph.
There is no other way which is the reason why constraints are set to just 1000