PROBLEM LINK: Is it Sorted or Not, That is the Question
AUTHOR: panik
DIFFICULTY: Easy-Medium
PREREQUISITES: Graph Theory, DFS
Solution: In This Problem, we can see that the maximum no. of connected
components that we can get if we had the opportunity to delete any kind of node (not
just the leaf node) we could have obtained the answer to be total no. of leaf nodes in
the graph ( We can prove that there always exist a way to get this many connected
components).
Now Since we can delete only the leaf node, so each operation
would result in one less connected component than the max we could have
obtained(count of leaf nodes), because after every operation 1 leaf node is
destroyed. So we choose only those leaf nodes whose destruction is
mandatory and their destruction results in the creation of at least 1 additional
connected component.
Now how to find the count of leaf nodes to be destroyed?
For this we need to observe that, there are 2 types of leaf nodes, 1) Such leaf nodes
whose parent has only leaf nodes as children and 2) whose parents have mixed
children(leaf node and non-leaf nodes).
For this Question, you also need to understand that such nodes that have only 1 child
can be compressed. eg. Tree of 7 nodes connections made like:
1 2
2 3
1 4
4 5
1 6
6 7
can be replaced with a tree of 4 nodes with connections like:
1 2
1 3
1 4
which is basically replacing linear chain of nodes with a single node,
and the answer to the above problem still remains the same i.e 2(we can delete any
leaf node and 2 components will remain).
So now let’s assume that whatever tree we get through input, we compress it using
the following property. Now coming back to the original question, we find the count of
all such nodes that have only leaf nodes as its children and subtract this count from
the max answer possible(total no. of leaf nodes). This method is correct because all
such nodes which have only leaf nodes as children have to have any one of its leaf
node destroyed to free the other leaf nodes.
Now we can avoid the compression of the tree by smartly implementing DFS only
once and finding all such nodes. So complexity is O(N).
Expected solution: here