[noip2015-提高] 信息传递

题目描述

$n$ 个同学每人有一个固定信息传递对象 $T_i$ （ $T_i \leq n$ ， $T_i \neq i$ ）。每轮所有人同时把已知的生日告诉自己的 $T_i$ 。当有人从别人口中听到自己的生日时游戏结束，求进行了多少轮。

思路

每人只有一条出边，图由若干链指向环组成。不在环上的点的生日永远不会回到自己，环上的点会在环长轮后第一次听到自己的生日。因此答案就是所有环长度的最小值。用三色标记（未访问/当前路径/已归档）沿出边走，每个点只走一次，遇到当前路径上的点即得到一个环。

参考代码

Python 版：

python

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
66
67
68#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 11:31
# update_at: 2026-10-02 11:52

import sys
from collections.abc import Iterator

N = 200000  # 题面 n 的上界，静态数组长度

to = [0] * (N + 1)    # to[i]：i 的信息传递对象（内向基环森林的出边）
color = [0] * (N + 1)  # 0 = 未访问，1 = 本轮在路上，2 = 已归档（含环与入链）


def read_ints(buf: bytes) -> Iterator[int]:
    """逐字节解析全部整数：split() 会一次造出 n 个小 bytes 对象，峰值内存顶破限制。"""
    num = 0
    in_num = False
    for b in buf:
        if 48 <= b <= 57:  # 数字位
            num = num * 10 + b - 48
            in_num = True
        elif in_num:       # 分隔符：收下刚攒完的数
            yield num
            num, in_num = 0, False
    if in_num:
        yield num


def rings(n: int) -> Iterator[int]:
    """从每个未访问点沿出边走到底，产出本轮新发现的环长。

    每人恰好一条出边，走到底必然撞上三种点：本轮在路上的点（自己的链闭成环）、
    已归档的点（走进别人的链/环，不产生新环）。环长 = 撞点在本轮路径中的位置到末尾。
    """
    for start in range(1, n + 1):
        if color[start]:
            continue  # 别人的链或环已覆盖，进去也找不到新环

        path: list[int] = []
        u = start
        while color[u] == 0:
            color[u] = 1  # 标"在路上"，链走到别处时立刻能认出
            path.append(u)
            u = to[u]

        if color[u] == 1:  # 撞回本轮标记：这条链自己闭成了环
            # 环长 = 撞点在路径中的位置到末尾；每个点只属于一条路径，总代价仍是 O(n)
            yield len(path) - path.index(u)

        for v in path:     # 归档整条链，之后任何链都不必再走第二遍
            color[v] = 2


def solve() -> None:
    data = read_ints(sys.stdin.buffer.read())
    n = next(data)
    for i in range(1, n + 1):
        to[i] = next(data)  # 题面的 T_i

    # 自己的生日只会沿环转回来：第 L 轮听到 = 自己在长 L 的环上，答案取最小环长
    print(min(rings(n)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2025-03-28 10:18
 * update_at: 2026-10-06 15:32
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 200000 + 5; // 最大人数

int n;              // 人数
int to[MAXN];       // to[i] 表示 i 的信息传递对象
int color[MAXN];    // 0 未访问，1 当前路径中，2 已处理完
int path[MAXN];     // 当前遍历经过的节点序列
int pos[MAXN];      // 节点在本轮 path 中的位置，0 表示未入栈
int ans;            // 最短环长度

// 三色标记找环：每个点只入栈、归档一次，时间 O(n)
void find_rings() {
    for (int start = 1; start <= n; ++start) {
        if (color[start] != 0) continue; // 已被处理过，跳过

        int u = start;
        int len = 0; // 当前 path 长度

        // 沿出边走，直到遇到非 0 节点
        while (color[u] == 0) {
            color[u] = 1;
            pos[u] = ++len;
            path[len] = u;
            u = to[u];
        }

        // 如果终止点是本轮路径上的点，说明形成了环
        if (color[u] == 1) {
            int ring_len = len - pos[u] + 1;
            if (ring_len < ans) ans = ring_len;
        }

        // 把本轮经过的所有点归档为已处理
        for (int i = 1; i <= len; ++i) {
            color[path[i]] = 2;
            pos[path[i]] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &to[i]);
    }

    ans = n + 1; // 初始化为比最大可能环长更大的值
    find_rings();

    printf("%d\n", ans);
    return 0;
}

[noip2015-提高] 信息传递

目录

题目描述

思路

参考代码