杭电ACM 找循环节 std::ios::sync_with_stdio(false);

浏览数：20 / 时间：2015年06月11日

Problem Description

As a unicorn, the ability of using magic is the distinguishing feature among other kind of pony. Being familiar with composition and decomposition is the fundamental course for a young unicorn. Twilight Sparkle is interested in the decomposition of permutations. A permutation of a set S = {1, 2, ..., n} is a bijection from S to itself. In the great magician —— Cauchy‘s two-line notation, one lists the elements of set S in the first row, and then for each element, writes its image under the permutation below it in the second row. For instance, a permutation of set {1, 2, 3, 4, 5} σ can be written as:

技术分享

Here σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, and σ(5) = 1.
Twilight Sparkle is going to decompose the permutation into some disjoint cycles. For instance, the above permutation can be rewritten as:

技术分享

Help Twilight Sparkle find the lexicographic smallest solution. (Only considering numbers).

Input

Input contains multiple test cases (less than 10). For each test case, the first line contains one number n (1<=n<=10^5). The second line contains n numbers which the i-th of them(start from 1) is σ(i).

Output

For each case, output the corresponding result.

Sample Input

Sample Output

(1 2 5)(3 4)
(1)(2)(3)

代码：

/*
*Copyright (c)2014,烟台大学计算机与控制工程学院
*All rights reserved.
*文件名称：test.cpp
*作    者：冷基栋
*完成日期：2015年2月6日
*版 本 号：v1.0
*问题描述：找循环节
*程序输入：一个整数n，和n个整数
*程序输出：相关的各组数
*/

#include <iostream>
#include <cstdio>
#include <cstring>
const int NUM=100001;
using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    int i,j,n,m;
    int a[NUM];
    while(cin>>n)
    {
        for(i=1; i<=n; i++)
            cin>>a[i];
        for(i=1; i<=n; i++)
        {
            while(a[i])
            {
                cout<<"("<<i;
                j=a[i];
                a[i]=0;
                while(a[j])
                {
                    cout<<" "<<j;
                    m=a[j];
                    a[j]=0;
                    j=m;
                }
                cout<<")";
            }
        }
        cout<<endl;
    }
    return 0;
}

运行结果：

技术分享

知识点总结：

cin，cout之所以效率低，是因为先把要输出的东西存入缓冲区，再输出，导致效率降低，而这段语句可以来打消iostream的输入输出缓存，可以节省许多时间，使效率与scanf与printf相差无几。std::ios::sync_with_stdio(false);（偷窥无罪哈哈）

学习心得：

好好学习天天向上

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

杭电ACM 找循环节 std::ios::sync_with_stdio(false);