📖 第 5.2b 章：函数图（Functional Graphs）

⏱ 预计阅读时间：35 分钟 | 难度：🟡 中等（USACO Silver 重要考点）

前置条件

BFS 与 DFS（第 5.2 章）
图的基本表示（第 5.1 章）

🎯 学习目标

学完本章后，你将能够：

识别函数图的特征结构（每节点恰好一条出边）
找到函数图中的所有环（环检测）
计算图中每个节点距离其所在环的步数
解决"从节点 x 出发走 k 步到哪里"的跳跃问题（含快速幂加速）
应用到 USACO Silver 中的函数图专题

5.2b.1 什么是函数图？

定义

函数图（Functional Graph） 是每个节点恰好有一条出边的有向图。

node[i] → next[i]，每个节点有且仅有一个后继节点。

等价地，函数图就是一个映射 f: {1..N} → {1..N}，从 i 走一步到 f(i)。

结构特征：ρ 形（rho 形）

由于每个节点只有一条出边，从任意节点出发最终必然进入环（因为节点有限，走无限步必然重复）。

典型结构（ρ 形）：

1 → 2 → 3 → 4 → 5
                ↑   ↓
                8 ← 6
                ↑
                7

节点 5, 6, 8 构成环
节点 1, 2, 3 是"尾巴"（最终进入环）
节点 4 是环的入口
节点 7 指向 8（悬挂在环上）

关键结论：

每个连通分量恰好包含一个环
其他节点都是"树"状悬挂在环上的

5.2b.2 找环（Floyd 判环 / 着色法）

方法一：着色法（推荐，适合 USACO）

用三种颜色追踪 DFS 状态（与有向图环检测完全相同）：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
int nxt[MAXN];      // nxt[i] = i 的后继节点
int color[MAXN];    // 0=未访问, 1=访问中, 2=已完成
int on_cycle[MAXN]; // on_cycle[i] = i 是否在环上
int cycle_id[MAXN]; // 所在环的编号（-1表示不在环上）
int dist_to_cycle[MAXN]; // 到所在环的距离（环上节点为0）

int n;
int num_cycles = 0;

void find_cycle(int start) {
    // 沿着出边走，找到环的起点
    vector<int> path;
    int cur = start;
    
    while (color[cur] == 0) {
        color[cur] = 1;   // 标记为"访问中"
        path.push_back(cur);
        cur = nxt[cur];
    }
    
    if (color[cur] == 1) {
        // cur 是环的入口，标记整个环
        int cycle = num_cycles++;
        int v = cur;
        do {
            on_cycle[v] = true;
            cycle_id[v] = cycle;
            dist_to_cycle[v] = 0;
            v = nxt[v];
        } while (v != cur);
    }
    
    // 将路径上的节点标记为"已完成"
    for (int v : path) color[v] = 2;
}

int main() {
    cin >> n;
    fill(cycle_id, cycle_id + n + 1, -1);
    fill(color, color + n + 1, 0);
    
    for (int i = 1; i <= n; i++) cin >> nxt[i];
    
    for (int i = 1; i <= n; i++)
        if (color[i] == 0) find_cycle(i);
    
    // 计算非环节点到环的距离（BFS 从环向外）
    queue<int> q;
    // 建反向图
    vector<vector<int>> rev(n + 1);
    for (int i = 1; i <= n; i++) rev[nxt[i]].push_back(i);
    
    for (int i = 1; i <= n; i++)
        if (on_cycle[i]) { dist_to_cycle[i] = 0; q.push(i); }
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : rev[u]) {
            if (!on_cycle[v] && dist_to_cycle[v] == 0 && v != u) {
                // 尚未计算距离
                dist_to_cycle[v] = dist_to_cycle[u] + 1;
                cycle_id[v] = cycle_id[u];  // 继承所在环
                q.push(v);
            }
        }
    }
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << "节点 " << i
             << (on_cycle[i] ? " [在环上]" : " [不在环上]")
             << "，到环距离=" << dist_to_cycle[i]
             << "，所在环=" << cycle_id[i] << "\n";
    }
    return 0;
}

方法二：Floyd 判环（快慢指针）

适合判断单条路径是否有环（不需要找具体哪个节点在环上）：

// Floyd 快慢指针判环
// 从节点 start 出发，判断是否存在环
bool has_cycle_floyd(int start) {
    int slow = start, fast = start;
    do {
        slow = nxt[slow];
        fast = nxt[nxt[fast]];
    } while (slow != fast);
    return true;  // 函数图一定有环（节点有限）
}

// 找环的入口节点（环起点）
int find_cycle_entry(int start) {
    int slow = start, fast = start;
    do {
        slow = nxt[slow];
        fast = nxt[nxt[fast]];
    } while (slow != fast);
    // 相遇后，slow 从 start 重新出发，fast 留在原地，同速走
    slow = start;
    while (slow != fast) {
        slow = nxt[slow];
        fast = nxt[fast];
    }
    return slow;  // 环的入口
}

5.2b.3 跳 k 步问题（倍增加速）

问题： 从节点 x 出发，走 k 步后到哪里？

朴素做法：循环 k 次，O(k) 可能很慢（k ≤ 10^18）。

倍增加速： 预处理 jump[v][j] = 从 v 出发跳 2^j 步后的节点，类似 LCA 倍增。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int LOG = 40;  // log2(10^18) ≈ 60，按需调整

int n;
long long nxt_arr[MAXN];
long long jump[MAXN][LOG];  // jump[v][j] = 从 v 走 2^j 步

void preprocess() {
    // 第 0 层：直接后继
    for (int v = 1; v <= n; v++) jump[v][0] = nxt_arr[v];
    // 倍增构建
    for (int j = 1; j < LOG; j++)
        for (int v = 1; v <= n; v++)
            jump[v][j] = jump[jump[v][j-1]][j-1];
}

// 从节点 v 出发，走 k 步
long long walk(long long v, long long k) {
    for (int j = 0; j < LOG; j++)
        if ((k >> j) & 1)
            v = jump[v][j];
    return v;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> nxt_arr[i];
    preprocess();
    
    int q; cin >> q;
    while (q--) {
        long long v, k;
        cin >> v >> k;
        cout << walk(v, k) << "\n";
    }
    return 0;
}

5.2b.4 USACO Silver 典型题型

题型 1：函数图的连通性

问题模式： 判断两个节点是否能相互到达，或最终是否落在同一环中。

解法： 找出每个节点所属的环（cycle_id[]），同一环 = 可以相互到达。

// 两节点 u, v 是否最终落在同一环？
bool same_cycle(int u, int v) {
    return cycle_id[u] == cycle_id[v] && cycle_id[u] != -1;
}

题型 2：从每个节点走恰好 k 步后的分布

// 统计走 k 步后，每个节点各有多少节点落在上面
vector<int> count_after_k_steps(int n, int k) {
    vector<int> cnt(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cnt[walk(i, k)]++;
    }
    return cnt;
}

5.2b.5 完整例题：奶牛跳跃（USACO Silver 风格）

题目： N 头奶牛编号 1~N，每头奶牛 i 喜欢奶牛 nxt[i]（构成函数图）。
定义「喜欢链」：从 i 出发沿喜欢关系走 k 步。
Q 次查询，每次给出 (i, k)，输出走 k 步后到达的奶牛编号。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005, LOG = 20;
int n, q;
int jump[MAXN][LOG];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> jump[i][0];
    
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i <= n; i++)
            jump[i][j] = jump[jump[i][j-1]][j-1];
    
    while (q--) {
        int v, k; cin >> v >> k;
        for (int j = 0; j < LOG; j++)
            if ((k >> j) & 1) v = jump[v][j];
        cout << v << "\n";
    }
    return 0;
}

⚠️ 常见错误

错误	原因	修复方案
死循环	朴素走 k 步但不考虑环	倍增法；或找到环后取模
jump 数组越界	jump[0][j] 未初始化（若节点编号从0开始）	确保哨兵节点正确
循环检测不完整	只检测从某个起点出发的路径	对所有未访问节点都执行 find_cycle
有向图判环用无向图方法	函数图是有向图	不能用「父节点排除法」

💪 练习题

🟢 题目 1：找所有环

给定函数图，输出所有环的节点集合（每行一个环，节点按访问顺序）。

✅ 完整解答

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> nxt(n + 1);
    for (int i = 1; i <= n; i++) cin >> nxt[i];
    
    vector<int> color(n + 1, 0);
    vector<bool> on_cycle(n + 1, false);
    
    for (int start = 1; start <= n; start++) {
        if (color[start] != 0) continue;
        
        vector<int> path;
        unordered_map<int,int> pos;  // 节点在 path 中的位置
        int cur = start;
        
        while (color[cur] == 0) {
            color[cur] = 1;
            pos[cur] = path.size();
            path.push_back(cur);
            cur = nxt[cur];
        }
        
        if (color[cur] == 1 && pos.count(cur)) {
            // 找到环：从 cur 开始到 path 末尾
            cout << "环：";
            for (int i = pos[cur]; i < (int)path.size(); i++) {
                on_cycle[path[i]] = true;
                cout << path[i] << " ";
            }
            cout << "\n";
        }
        
        for (int v : path) color[v] = 2;
    }
    return 0;
}

🟡 题目 2：走 k 步

给定函数图和 Q 次查询 (v, k)，每次输出从 v 出发走 k 步后的节点（k ≤ 10^9）。

✅ 完整解答

直接使用 5.2b.3 的倍增模板（LOG=30 处理 k≤10^9）。

🔴 题目 3：最远公共祖先（函数图上的 LCA）

函数图中，定义节点 u 和 v 的「公共后继」为第一个同时是 u 的后继和 v 的后继的节点。
给 Q 次查询，找 (u, v) 的最近公共后继。

✅ 解题思路

先找每个节点所属的环及到环的距离 dist_to_cycle[v]
若 u, v 在同一个环：最近公共后继就在环上，用倍增在环上找
若在不同环：无公共后继（输出 -1）
若一个在环外，先让环外的走 dist_to_cycle[v] 步进入环，再求环上的公共后继

// 核心：把两节点都走到相同位置后，找第一个相同节点
int lca_in_func_graph(int u, int v) {
    // 让 u 和 v 距离环相同（先走到距离较大的那个）
    if (dist_to_cycle[u] < dist_to_cycle[v]) swap(u, v);
    u = walk(u, dist_to_cycle[u] - dist_to_cycle[v]);  // 使两者到环距离相同
    
    // 同步走直到相遇
    for (int j = LOG - 1; j >= 0; j--)
        if (jump[u][j] != jump[v][j]) { u = jump[u][j]; v = jump[v][j]; }
    
    if (u == v) return u;
    return jump[u][0];  // 下一步相遇
}

💡 章节联系： 函数图是 USACO Silver 的独特题型，每季赛约出现 1 道。它结合了图遍历（第 5.2 章）和 LCA 倍增（第 5.4 章）的思想，是 Gold 拓扑排序（第 8.2 章）的前置知识。

C++ 竞赛编程：USACO 学习指南