Editorial for DMOPC '22 Contest 3 P2 - New Components


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: yzhao123

First, note that all graphs formed by permutations are composed of a bunch of different cycles. Also, we can only create new components by disconnecting existing cycles, because nodes in the query set S cannot attach to themselves or each other to create new ones. For all 1 \le i \le N, let node i be pointing towards node P_i. Consider a node x in S. We can delete the edge from x to P_x if we reroute it backwards to the node which is pointing to x, essentially making the edge meaningless. Deleting D edges in a cycle will create D-1 new components. However, we can only delete an edge from x to P_x if the node pointing to x is not in the query set, because 2 nodes in S cannot be connected with an edge. So if the node pointing to x is also in S, then x cannot disconnect the component further, and we just attach x to another existing component. This does not affect the answer. Thus, we can find how many new components we can create from a cycle by counting the number of edges we can delete.

Subtask 1

The initial graph is 1 big cycle, so our initial answer is 1 component. Let D be the number of edges we can delete. We know that deleting D edges in a cycle will create D-1 new components. Adding D-1 to the initial answer 1, we get D as the final answer.

Subtask 2

Let the initial number of cycles be C. For each component that contains a node in the query set S, we can find D, and add D-1 to the answer. However, we do not actually need to consider each component independently. Notice that for each component, we always just subtract 1. So to find the number of new components, we can just find the total D value then subtract the number of components affected. Add this to the initial answer C to get the final answer.


Comments

There are no comments at the moment.