# 独角兽与数列（置换群循环）- HDU 4985

1. 封闭性： 对于所有G中a, b，运算a·b的结果也在G中。

2. 结合性： 对于所有G中的a, b和c，等式 (a·b)·c = a· (b·c)成立。

3. 单位元： 存在G中的一个元素e，使得对于所有G中的元素a，等式e·a = a·e = a成立。

4. 逆元： 对于每个G中的a，存在G中的一个元素b使得a·b = b·a = e，这里的e是单位元。

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:

TS准备拆解这个组合成一些不相连的循环组，比如，上面的排列可以这样写：

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

```5
2 5 4 3 1
3
1 2 3```

Sample Output

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

```#include <stdio.h>
#include <string.h>

int main()
{
int n;
//小于10的5次方
int values[100017], flags[100017];

while (~scanf("%d", &n))
{
//
memset(flags, 0, sizeof(flags));
//依次输入组合
for (int i = 1; i <= n; i++)
{
scanf("%d", &values[i]);
}

//寻找所有环状数列
for (int i = 1; i <= n; i++)
{
//如果f[i]有值了，说明已经在某个环状集合里面了，继续寻找没有处理的元素
if (flags[i])
continue;

//标记第一个数
int j = i;
flags[j] = 1;
printf("(%d", j);
//寻找环状数列
while (flags[values[j]] == 0)
{
printf(" %d", values[j]);
//标记以寻找
flags[values[j]] = 1;
//寻找下一个
j = values[j];
}
printf(")");
}
printf("\n");
}

return 0;
}```

0 条评论

• ### 搜索专题4 | 旋转棋盘 POJ - 2286

The rotation game uses a # shaped board, which can hold 24 pieces of square bloc...

• ### 除以3，乘以2（STL+排序）- Codeforces 997D

Polycarp likes to play with numbers. He takes some integer number x, writes it d...

• ### Planning mobile robot on Tree (EASY Version)（UVA12569，状态压缩)

题目链接：https://vjudge.net/problem/UVA-12569

• ### 【UVALive 3905】BUPT 2015 newbie practice #2 div2-D-3905 - Meteor

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=102419#problem/D

• ### HDOJ 1194 Beat the Spread!（简单题）

Problem Description Superbowl Sunday is nearly here. In order to pass the time...

• ### Codeforces Round #622 (Div. 2) 1313 C1

C1. Skyscrapers (easy version) time limit per test1 second memory limit per te...

• ### Gazebo機器人仿真學習探索筆記（四）模型編輯

模型編輯主要是自定義編輯物體模型構建環境，也可以將多種模型組合爲新模型等，支持外部模型導入，

• ### ABAP如何在调试查看EXPORT/IMPORT 内存数据

These memory IDs can be accessed in the debugger, but the option isn't accessibl...

Railroad Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

• ### Codeforces 1291 Round #616 (Div. 2) C. Mind Control（超级详细）

You and your n−1 friends have found an array of integers a1,a2,…,an. You have de...