Interesting Graph Permutations Problem.

Revision en1, by MedoN11, 2016-12-07 03:01:11

Hello CF.

Recently, I was trying to solve this problem : https://community.topcoder.com/stat?c=problem_statement&pm=10469&rd=13749&rm=&cr=22697731.

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English MedoN11 2016-12-07 03:01:11 905 Initial revision (published)