i have made dsu , in rank rather updating rank of parent i have updated the rank of that element and at last run a for loop checking which all elements have large rank than element 1.
My logic is correct or not
I don’t think DSU can be used with this problem because the whole point of DSU is that elements in a particular component are all interlinked but in this only the parents and their immediate children are linked.
According to me problem is a simple implementation of DFS while maintaining a count of children of the vertices visited. Let u be a vertex and v be its child. Then, check if children[v]>children[u].This way, check for each vertex while traversing the graph in DFS. One important thing to note that actually there are many trees in the input(a graph with no cycles and self-loops is a tree). That means you have to apply DFS for each of these trees.
You can check this for implementation https://ide.codingblocks.com/s/333816
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.