The Bovine Shuffle

$$\bold T\bold h\bold e\ \bold B\bold o\bold v\bold i\bold n\bold e\ \bold S\bold h\bold u\bold f\bold f\bold l\bold e$$

---

翻译(非机翻 机翻也翻不出这么有才的题解 )

题目描述

$\bold F\bold J$坚信快乐的牛可以产出更多的牛奶，因此$\bold F\bold J$在牛棚里安装了一个巨大的迪斯科球并且打算让奶牛们学会跳舞。
$\bold F\bold J$在许多出名的奶牛舞中选择了一种叫做 Shuffle Bovine Shuffle 的舞蹈。这种舞蹈由 $\bold F\bold J$的$N$头奶牛组成。$N$头奶牛以一种顺序排成一行，接着表演数次 Shuffle。每次的 Shuffle 会将奶牛重新排列。$\bold F\bold J$为了让奶牛们更加快乐，让奶牛们更容易找到重新排列后的位置，他标记了 $N$ 头奶牛的位置。在最开始，所有奶牛排成一排，第一头奶牛会在位置 $1$ 上，第二只在 $2$上，以此类推。
我们用$N$个正整数$a_1,a_2,a_3,...,a_n$来描述每次的Shuffle。$a_i$说明了在位置$i$上的奶牛在经过这回合的Shuffle，会跑到位置$a_i$上。令$\bold F\bold J$倍感非洲的是,即使$i$与$j$不同，$a_i$也有可能会等于$a_j$！所以有可能在一次Shuffle后，有多头奶牛会跑到同一位置上，在这之后这群奶牛也会一同行动。
作为一名资深的坑牛砖家养牛大户,$\bold F\bold J$猛然发现，无论经过多少次的Shuffle，一直都有$k$个位置上有奶牛，$\bold F\bold J$现在要你在一秒之内算出$k$的值，否则就赏你$10^{18}\bold m\bold o\bold d 10$大板！

输入格式

第一行包含一个整数 $N$
第二行包含$N$个整数，描述题目中的$a_1,a_2,a_3,...,a_n$

输出格式

一个整数,代表$k$

输入输出样例

输入#1

4
3 2 1 3

输出#2

3

---

思路

这道题其实要求出所有环的长度之和。
至于为什么，我们把牛的移动方向看做连箭头，那么就变成了一个有向图。
那么一个环里面的牛就会不停的交换位置，不会重叠。但是如果有某个点指向了环的某一个地方，这个点的牛就会和环里面的牛重叠。
所以我们只要找出不在环里面的点，然后统计出所有环的长度之和就可以了。

AC代码

#include<cstdio>
#include<cstring>

using namespace std;

int n, a, to[1000001], ru[1000001], ans;
bool in[1000001], in2[1000001];

void dfs(int now) {
	in[now] = 1;
	ru[to[now]]--;
	if (!ru[to[now]]) dfs(to[now]);
}

int dfs1(int now) {
	if (in2[now]) return 0;
	in2[now] = 1;
	return 1 + dfs1(to[now]);
}

int main() {
//	freopen("shuffle.in", "r", stdin);
//	freopen("shuffle.out", "w", stdout);
	
	scanf("%d", &n);//读入
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a);//读入
		to[i] = a;//连边
		ru[a]++;//记录入读数
	}
	
	for (int i = 1; i <= n; i++)
		if (!ru[i] && !in[i]) dfs(i);//找出不在环内的点
	for (int i = 1; i <= n; i++)
		if (!in2[i] && !in[i]) ans += dfs1(i);//统计在环中的点的数量
	
	printf("%d", ans);//输出
	
//	fclose(stdin);
//	fclose(stdout);
	
	return 0;
}

欢迎加入团队