I am getting wrong answer. Can you provide test cases where my code is not working?
Beautiful Vertices - WA
@koshimagoyal97
The test cases are large it can’t be provided here.
I went through your code,you are not applying DFS properly.
Why to use DFS?
As we have to check for each vertex and there are no self loops.
@mailmeanmolbansal
I haven’t used DFS in this.
My logic is first find child(neighbours) of minimum vertex which is the master parent. After that finding child(neighbours) of other vertex present and comparing it to master parent’s child. I am simply using ArrayList and traversing in the keyset.
@koshimagoyal97
Sorry for the late response.
You are assuming master_size same as the minimum vertex,which is actually correct for one vertex only.
Please read the highlighted line,Beautiful Vertex is defined as that vertex which has more children than its parent and you interpreted the definition wrong.You treated master_parent as the the parent of all the vertices.
But every vertex has its own different parent and children..
Let me clarify more:
Simply Consider this N=10,E=9
This may clarify your doubt,please hit like if i gave a satisfactory response to your doubt and try to use DFS as without completely traversing the Graph we can’t judge the beautiful vertex.
2 Likes
@mailmeanmolbansal
Thanks alot. I tried to rectify my mistake but I am still not able to figure out that how to keep track of who is parent of whom?
@koshimagoyal97
In BFS/DFS,The problem we have is we can refer the children of a node but we can’t refer what was the parent of this node.
Lets discuss an approach,
Traverse the complete tree once and mantain a HashMap <Node,Integer> and in the postorder,that is after traversing the children of a particular node,if any put the count of that particular node in HashMap.
Now we have a map in which every node has its count of children.
Traverse the tree again,BFS or DFS any way of traversal, and compare every node’s with its children using map.get(),if more count++ else go to next node and do it for every other nodes.
And the time complexity is O(n) per test case.
if it helps please hit a like and if it doesn’t Come back up with updated code.
@mailmeanmolbansal
Sorry but still it is not clear. I understand that we are maintaining HashMap for that but while processing how will we ensure that the node that we are processing is child of which parent and if we are not able to figure out so, then how will I use map.get()??
One more thing why to do post order when for loop will be helpful in maintaining count of children.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.