「NOIP2015」信息传递

发表于 | 分类于

使用拓扑求最大环长度；

题目链接

有 n 个同学（编号为 1 到 n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 T_i 的同学。

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

格式

输入格式
输入共 2 行。

第 1 行包含 1 个正整数 n，表示 n 个人。

第 2 行包含 n 个用空格隔开的正整数 T_1T , T_2T, … … , T_nT，其中第 i 个整数T_iT 表示编号为 i 的同学的信息传递对象是编号为 T_iT
T_iT≤ n 且 T_iT ≠ i。

数据保证游戏一定会结束。

输出格式
输出共 1 行，包含 1 个整数，表示游戏一共可以进行多少轮。

样例1
样例输入1

5
2 4 2 3 1

样例输出1

3

限制
对于 30%的数据， n ≤ 200；

对于 60%的数据，n ≤ 2500；

对于 100%的数据，n ≤ 200000。

提示
【输入输出样例 1 说明】

此处输入图片的描述

游戏的流程如图所示。当进行完第 3 轮游戏后，4 号玩家会听到 2 号玩家告诉他自己的生日，所以答案为 3。当然，第 3 轮游戏后，2 号玩家、3 号玩家都能从自己的消息来源得知自己的生日，同样符合游戏结束的条件。

来源
NOIP 2015 提高组 Day 1 第二题

读完这道题之后，我们想一下，有对象关系， 有传递关系，那么我们就可以把信息存到一份图里！> . <

存完图之后，思考一下，如果自己的生日信息能传回自己，那么他就存在于一个环里（注意:图中可能存在多个环）。我们首先用拓扑把不在环上的点打上标记，然后再求所有环中的 最长环的长度，就是游戏可进行的最大轮数了。问题解决了！

本题是有向图，我们使用拓扑来解决问题；

附上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <iostream>
#include <cctype>
#include <queue>
using namespace std;
#define DEBUG(x) std::cerr << #x << " = " << x <<std::endl
#define max(x, y) ((x) > (y) ? x : y)
inline int read() {
	char ch = getchar(); int res = 0; int flag = 1;
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') flag = -1;
	for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + ch - '0';
	return (res * flag);
}//快读
int n, ans, tot, ver[200007], per[200007];
//ver[]数组存储“父亲”数量
//per[]数组存储传递对象
bool vis[200007];//为节点打标记
queue<int>que;
int main() {
	ans = 0x7fffffff;
	tot = 0x7fffffff;
	n = read();
	for(int i = 1; i <= n; i++) {
		int x = read();
		per[i] = x;
		ver[x] ++;
	} 
	for(int i = 1; i <= n; i++) {
		if(ver[i] == 0) {
			vis[i] = 1;
			que.push(i);
		}
	}
	while(!que.empty()) {
		int cnt = que.front();
		que.pop();
		ver[per[cnt]] --;
		if(ver[per[cnt]] == 0) {
			vis[per[cnt]] = 1;
			que.push(per[cnt]);
		}
	}
	//为所有不在环上的点打上标记
	for(int i = 1; i <= n; i++) {
		if(vis[i] == 0 && ver[i] != 0) {
			vis[i] = 1;
			tot = 1;
			int j = per[i];
			while(!vis[j]) {
				vis[j] = 1;//每个点只有唯一一个传递对象，所以它只存在于一个环上，所以在此时遍历到它，便可以直接打上标记；
				j = per[j];
				tot ++;//记录此环的长度
			}
		}
		if(tot < ans) ans = tot;
	}
	//求最长环长度
	printf("%d\n", ans);
	return 0;
}