MINIKILL Enigma Editorial

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

1 Like

can u tell how dfs can help in determining the nodes having leaf nodes as children…i can understand your modified dfs code

@panik Can you please explain the implementation of DFS in your solution? It is not clear from the code.

@panik can I get some help to check my solution here? codechef.com/viewsolution/29258435

My solution:

We try to delete root of subtree and find the ans:
if we remove the root we kill at least one child.

If killing a child-node has at least 1 non-zero component in the child’s subtree we kill this and other only if they result have >= 1 components if required

other wise we kill only one of the child
result = number of children - 1(killed child)

not-killing the root always result in 1 component for subtree

Implementation can be done in 1-pass dfs.

dfs(v): returns maximum number of components resulting by killing the root
int dfs(int v, int par = -1)
{
    vector<int> child_kill;
    for (int x: adj[v])
    {
        if (x != par)
        {
            child_kill.push_back(dfs(x, v));
        }
    }
    int mv = 0;
    for (int x: child_kill)
        mv = max(x, mv);
    int ans = 0;
    if (mv > 0)
    {
        for (int x: child_kill)
            ans += max(x, 1);
    }
    else
    {
        ans = child_kill.size() - 1;
    }
    ans = max(ans, 0);
    return ans;
}

final_ans = max(1, dfs(1))

AC: https://www.codechef.com/viewsolution/35890950