置换群与轮换

昨晚BestCoder第一题：

 

一开始看了半天不知所云2333333

其实它是让求置换群的轮换

比如对于原题中的

有o(1)=2, o(2)=5, o(3)=4, o(4)=3, o(5)=1

其中o(1)=2,o(2)=5,o(5)=1就是一个轮换，转了一圈之后又回来了233

同理，o(3)=4, o(4)=3又是一个轮换。

所以输出答案为(1 2 5)(3 4)

---------------------------------------------------------------------------------

挺水的一个水题，结果不知道为什么我的代码总是TLE   T^T

终于知道为什么了T^T

while (~scanf(......))

注意加上那个～

因为OJ上读入结束之后scanf返回值是-1（即二进制11111111），加个～就可以让循环结束了

很隐蔽的bug......手测根本发现不了T^T

 

附代码

#include "stdio.h"
int a[100010];
int v[100010];
int tx,ty,n,i;

int main()
{
    while (~scanf("%d\n",&n))
    {
        for (i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            v[i]=0;
        }
        for (i=1;i<=n;i++)
        {
            if (v[i]==0)
            {
                printf("(%d",i);
                v[i]=1;
                tx=i;
                ty=a[i];
                while (v[ty]==0)
                {
                    printf(" ");
                    v[ty]=1;
                    tx=ty;
                    ty=a[ty];
                    printf("%d",tx);
                }
                printf(")");
            }
        }
        printf("\n");
    }
    return 0;
}

 

 

Orz