Please subscribe to the official Codeforces channel in Telegram via the link ×

MedoN11's blog

By MedoN11, history, 7 years ago, In English

Hello CF.

Recently, I was trying to solve this problem :

Please note, this problem doesn't have an editorial. ( It's magically still coming soon even though it's from 2009).

I was constructing a functional graph G where an edge from node i to node j, means that the ith index contains the jth value.

Then, The graph must all of it lie in one cycle ( one SCC ) for the conditions to hold. Otherwise answer ( number of swaps ) is #SSC's — 1. Each component must be linked to another and only one.

The problem however lies in constructing the permutation. I was following an approach that involves greedily merging components starting from the first component that contains zero, but I keep getting WA on a large case.

Any help would be appreciated.

  • Vote: I like it
  • +2
  • Vote: I do not like it