Interesting Graph Permutations Problem.

Правка en1, от MedoN11, 2016-12-07 03:01:11

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.


  Rev. Язык Кто Когда Δ Комментарий
en1 Английский MedoN11 2016-12-07 03:01:11 905 Initial revision (published)