One_Liner's blog

By One_Liner, history, 4 weeks ago, In English

How to solve WeirdSort problem via the tag "dfs and similar"?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It is given that we are allowed to swap elements present at given index. Model the question as a graph having edges between these indexes and then find the connected components for all the indexes. Now, sort the array and see if the component of the index of the number that is present at index i in the sorted array is same as the component of index i itself.

My code using the above idea: https://codeforces.com/contest/1311/submission/85116001