## Editorial for DMOPC '22 Contest 3 P2 - New Components

**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:

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 cannot attach to themselves or each other to create new ones. For all , let node be pointing towards node . Consider a node in . We can delete the edge from to if we reroute it backwards to the node which is pointing to , essentially making the edge meaningless. Deleting edges in a cycle will create new components. However, we can only delete an edge from to if the node pointing to is not in the query set, because nodes in cannot be connected with an edge. So if the node pointing to is also in , then cannot disconnect the component further, and we just attach 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 big cycle, so our initial answer is component. Let be the number of edges we can delete. We know that deleting edges in a cycle will create new components. Adding to the initial answer , we get as the final answer.

#### Subtask 2

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

## Comments