spoj1421专题

spoj1421 - Goods(循环节)

暑假个人赛第二场D - Goods 题意:给定一个乱序的排列,要求重排成1~n的顺序,且调换方式为: 每次只能两个数字对换,每轮可以对换任意多次,但每轮中每个数字只能对换一次, 问需要几轮才能达到最终要求。 思路:找出所有的循环节, 若循环节长度为1,则不需要交换 若循环节长度为2,很明显的一轮就可以搞定, 若循环节的长度>2的话,就需要2轮了, 每找 出一个循环节就进行一轮的交换