I have applied dfs on graph and storing the children and parent of each node in dfs call. After dfs completes I am checking the children of parent and node but its actually counting the children wrong
For given case my code is counting 1 has 4 children including itself but it should be 1 has 2 children including itself
Not able to pass the sample test case
In this code I have used outdegree approach considering it as a directed and undirected graph…The sample test case passed but other are getting wrong answers
@piyush.bansal8158625 You are doing mistake in your DFS helper function. See, according to the sample case, the graph would be like this:
According to your DFS helper function and by your line 27: children[node]+=dfsHelper(neighbour,visited,children);
node 1 will have 4 children ie. itself, 2, 3, and 4. Note that this is a recursive function and if you call dfshelper while on node 1… line 27 would be like: children[1]+=dfshelper(2,visited,children). Now dfshelper(2,vistited,children) would clearly return 3. So children[1] becomes 4. Try to think in the recursive way and you will get your mistake.
Anyway i am sharing how exactly the DFS and the DFShelper function would be modified for this problem. Dry run this code to know how its working. https://ide.codingblocks.com/s/145247
Sorry for the late response.
Hope this helps 
mast samjhaya ekdum… Thanks…doubt resolved for counting children as well
1 Like