Wiki › Thuật toán › Thuật toán đồ thị › Đồ thị hàm (Functional Graph)

Đồ thị hàm (Functional Graph)

huunguyen Updated Tháng 9. 29, 2026 Đọc 20 phút 2 lượt xem

Đồ thị hàm (functional graph) là đồ thị có hướng mà mỗi đỉnh có đúng một cạnh đi ra: đỉnh $v$ đi tới $f (v)$ . Nó xuất hiện khắp nơi dưới nhiều vỏ bọc: "cổng dịch chuyển ở mỗi hành tinh", "nhân viên $i$ ghét nhân viên $p_{i}$ ", "trạng thái hiện tại quyết định hoàn toàn trạng thái kế tiếp". Nắm được hình dạng của nó, ta tìm mọi chu trình trong $O (N)$ , trả lời "đi đúng $k$ bước thì tới đâu" với $k$ tới $10^{18}$ trong $O (\log k)$ thay vì $O (k)$ , và mô phỏng $T = 10^{9}$ bước với số bước thực sự phải chạy chỉ cỡ số trạng thái $S$ (không quá khoảng $2 S$ ).

Ý tưởng / Trực giác

Hình dạng "chữ rho"

Xuất phát từ một đỉnh $x_{0}$ bất kỳ và đi liên tục: $x_{0}, x_{1} = f (x_{0}), x_{2} = f (x_{1}), \dots$ Vì chỉ có $N$ đỉnh, sau tối đa $N$ bước ta chắc chắn gặp lại một đỉnh cũ (nguyên lý chuồng bồ câu). Và vì mỗi đỉnh chỉ có một cạnh ra, từ lúc gặp lại, đường đi lặp y hệt mãi mãi. Dãy vì thế có dạng chữ $ρ$ (rho): một đuôi dài $μ$ bước, rồi một chu trình dài $λ$ .

x0 -> x1 -> ... -> x(mu) -> ... -> x(mu+lambda-1)
                     ^                  |
                     +------------------+
        đuôi (mu bước)      chu trình (lambda đỉnh)

Nhìn toàn bộ đồ thị: mỗi thành phần liên thông (bỏ qua chiều cạnh) chứa đúng một chu trình, và các đỉnh còn lại tạo thành những cây treo vào các đỉnh của chu trình, cạnh hướng về phía chu trình. Lý do: thành phần có $k$ đỉnh thì có đúng $k$ cạnh, nên nó là "cây cộng thêm một cạnh", tức có đúng một chu trình.

Từ hình dạng này suy ra ba điều quan trọng:

Đỉnh nằm trên chu trình chính là các đỉnh không bao giờ "bị bỏ đi" nếu ta liên tục xóa những đỉnh không ai trỏ tới (bậc vào bằng 0). Đỉnh trên cây luôn có một lá phía dưới để bắt đầu "gọt" dần, còn đỉnh trên chu trình luôn được một đỉnh khác trên chu trình trỏ vào.
Đi $k$ bước là phép lặp $f^{k} (v)$ . Vì $f^{a + b} = f^{a} \circ f^{b}$ , ta có thể ghép các cú nhảy lũy thừa của 2, đúng như Binary Lifting trên cây, chỉ khác là ở đây "cha" của $v$ là $f (v)$ và không bao giờ hết đường để đi.
Mô phỏng một hệ tất định (trạng thái sau chỉ phụ thuộc trạng thái trước) cũng là đi trên đồ thị hàm của các trạng thái. Nếu số trạng thái hữu hạn, hệ chắc chắn rơi vào chu trình, và khi đã ở trong chu trình dài $λ$ thì vị trí sau $T$ bước chỉ phụ thuộc $T mod λ$ .

Tìm chu trình: hai cách $O (N)$

Xóa đỉnh bậc vào 0 (kiểu Kahn). Đếm bậc vào, cho mọi đỉnh bậc vào 0 vào hàng đợi, lần lượt xóa và giảm bậc vào của $f (u)$ . Đỉnh còn lại (bậc vào $> 0$ ) là đỉnh trên chu trình. Thứ tự xóa còn là một thứ tự tô pô của phần cây, rất tiện để tính độ sâu.
Tô màu 3 trạng thái. Mỗi đỉnh có màu: 0 = chưa thăm, 1 = đang nằm trên đường đi hiện tại, 2 = đã xử lý xong. Từ mỗi đỉnh chưa thăm, đi theo $f$ và tô màu 1. Nếu chạm đỉnh màu 1 thì ta vừa khép một chu trình mới (đi vòng từ đỉnh đó sẽ liệt kê được nó). Nếu chạm đỉnh màu 2 thì đường này chỉ đổ vào một phần đã biết, không có chu trình mới. Cuối cùng tô cả đường thành màu 2. Mỗi đỉnh được tô màu 1 đúng một lần (các đỉnh trên chu trình mới được đi thêm một vòng để liệt kê), nên tổng số bước là $O (N)$ .

Thuật toán Floyd "rùa và thỏ"

Khi không thể lưu mảng đánh dấu (không gian trạng thái quá lớn, hoặc chỉ có hàm $f$ ), dùng hai con trỏ: rùa đi 1 bước, thỏ đi 2 bước mỗi lượt.

Pha 1: khi cả hai đã vào chu trình, khoảng cách từ thỏ tới rùa (theo chiều đi) giảm đúng 1 mỗi lượt, nên chúng chắc chắn gặp nhau sau không quá $λ$ lượt nữa. Gọi $i$ là số lượt khi gặp: $x_{i} = x_{2 i}$ , nghĩa là $i$ là một bội của $λ$ và $i \geq μ$ .
Pha 2: đưa rùa về $x_{0}$ , giữ thỏ ở $x_{i}$ , cho cả hai cùng đi 1 bước. Sau $μ$ bước rùa ở $x_{μ}$ , thỏ ở $x_{μ + i}$ ; vì $i$ là bội của $λ$ nên hai vị trí trùng nhau, và đây là lần gặp đầu tiên. Đếm số bước được $μ$ .
Pha 3: từ $x_{μ}$ đi tiếp tới khi quay lại chính nó, đếm được $λ$ .

Bộ nhớ chỉ $O (1)$ .

Ví dụ chạy tay

Xét $N = 9$ với $f = [2, 3, 4, 5, 3, 2, 6, 9, 8]$ (tức $f (1) = 2, f (2) = 3, \dots, f (9) = 8$ ):

7 --> 6 --+
          v
1 ------> 2 --> 3 --> 4          8 <--> 9
                ^     |
                |     v
                +---- 5

Có hai thành phần: chu trình ${3, 4, 5}$ với cây ${1, 2, 6, 7}$ treo vào đỉnh 3, và chu trình ${8, 9}$ không có cây.

Cách 1: xóa đỉnh bậc vào 0

Bậc vào ban đầu:
đỉnh :  1  2  3  4  5  6  7  8  9
indeg:  0  2  2  1  1  1  0  1  1
Hàng đợi = [1, 7]

Xóa 1 -> indeg[2] = 1                 hàng đợi = [7]
Xóa 7 -> indeg[6] = 0, đẩy 6          hàng đợi = [6]
Xóa 6 -> indeg[2] = 0, đẩy 2          hàng đợi = [2]
Xóa 2 -> indeg[3] = 1                 hàng đợi = []

Thứ tự xóa: 1, 7, 6, 2
Còn lại (indeg > 0): 3, 4, 5, 8, 9   <- đúng là các đỉnh trên chu trình

Duyệt thứ tự xóa ngược lại (2, 6, 7, 1), mỗi đỉnh lấy thông tin từ $f (u)$ đã tính xong: $d e p t h [2] = 1$ , $d e p t h [6] = 2$ , $d e p t h [7] = 3$ , $d e p t h [1] = 2$ , cả bốn có gốc (đỉnh chu trình mà nó đổ vào) là 3.

Cách 2: tô màu 3 trạng thái

Bắt đầu từ 1:  1(màu1) -> 2(màu1) -> 3(màu1) -> 4(màu1) -> 5(màu1) -> 3 ĐANG MÀU 1
               => chu trình mới: 3 -> 4 -> 5 -> 3.  Tô 1,2,3,4,5 thành màu 2.
Bắt đầu từ 6:  6(màu1) -> 2 đã MÀU 2  => không có chu trình mới. Tô 6 màu 2.
Bắt đầu từ 7:  7(màu1) -> 6 đã MÀU 2  => không có chu trình mới.
Bắt đầu từ 8:  8(màu1) -> 9(màu1) -> 8 ĐANG MÀU 1
               => chu trình mới: 8 -> 9 -> 8.

Floyd từ $x_{0} = 1$

Dãy: $x_{0} . . x_{8} = 1, 2, 3, 4, 5, 3, 4, 5, 3$ .

Pha 1 (rùa +1, thỏ +2):
  lượt 1: rùa = x1 = 2, thỏ = x2 = 3
  lượt 2: rùa = x2 = 3, thỏ = x4 = 5
  lượt 3: rùa = x3 = 4, thỏ = x6 = 4   <- gặp nhau, i = 3 (bội của lambda = 3)
Pha 2 (rùa về x0, cả hai +1):
  rùa 1, thỏ 4 -> rùa 2, thỏ 5 -> rùa 3, thỏ 3   <- gặp tại đỉnh 3, mu = 2
Pha 3: từ 3 đi 3 -> 4 -> 5 -> 3, lambda = 3

Đi đúng $k = 10$ bước từ đỉnh 1 (binary lifting)

Bảng $u p [j] [v] = f^{2^{j}} (v)$ :

$v$	1	2	3	4	5	6	7	8	9
$u p [0]$ (1 bước)	2	3	4	5	3	2	6	9	8
$u p [1]$ (2 bước)	3	4	5	3	4	3	2	8	9
$u p [2]$ (4 bước)	5	3	4	5	3	5	4	8	9
$u p [3]$ (8 bước)	3	4	5	3	4	3	5	8	9

$10 = 1010_{2} = 2 + 8$ :

v = 1
bit 1 bật: v = up[1][1] = 3     (đã đi 2 bước)
bit 3 bật: v = up[3][3] = 5     (đã đi 2 + 8 = 10 bước)
Đáp án: 5.   Kiểm tra: x10 = 5 (dãy 1,2,3,4,5,3,4,5,3,4,5)

Mô phỏng rồi tua nhanh bằng chia lấy dư

Trạng thái $s \in {0, \dots, 9}$ , $s \to (s^{2} + 1) mod 10$ , bắt đầu $s = 3$ , hỏi trạng thái sau $T = 100$ bước. Ghi lại thời điểm đầu tiên gặp mỗi trạng thái:

t         :  0  1  2  3  4  5  6  7
trạng thái:  3  0  1  2  5  6  7  0   <- 0 đã gặp ở t = 1
seen[0] = 1, hiện tại t = 7  =>  độ dài chu trình = 7 - 1 = 6
Còn lại 100 - 7 = 93 bước, 93 mod 6 = 3
Đi thêm 3 bước từ 0: 0 -> 1 -> 2 -> 5
Đáp án: 5

Chỉ mô phỏng $7 + 3 = 10$ bước thay vì 100 bước; với $T = 10^{9}$ số bước mô phỏng vẫn không vượt quá khoảng hai lần số trạng thái.

Cài đặt

Phân rã đồ thị hàm: chu trình, gốc, độ sâu

Chương trình đọc $n$ và $f (1 . . n)$ , tìm các chu trình bằng cách xóa đỉnh bậc vào 0, rồi tính cho mỗi đỉnh: chu trình chứa gốc (cycId), gốc root, độ sâu depth (số bước tới chu trình), vị trí pos trên chu trình. Ví dụ ở cuối in "số bước tới khi gặp lại một đỉnh đã thăm" $= d e p t h + | chu trình |$ .

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> f(n + 1);
    for (int v = 1; v <= n; v++) cin >> f[v];

    // Remove vertices with in-degree 0 repeatedly (Kahn).
    vector<int> indeg(n + 1, 0), order;
    for (int v = 1; v <= n; v++) indeg[f[v]]++;
    queue<int> q;
    for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.push(v);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        if (--indeg[f[u]] == 0) q.push(f[u]);
    }
    // Vertices with indeg > 0 are exactly the cycle vertices.

    vector<int> cycId(n + 1, -1), pos(n + 1, 0), root(n + 1), depth(n + 1, 0);
    vector<vector<int>> cycles;
    for (int v = 1; v <= n; v++) {
        if (indeg[v] == 0 || cycId[v] != -1) continue;
        int id = cycles.size();
        cycles.push_back({});
        int u = v;
        do {                          // walk around the cycle once
            cycId[u] = id;
            pos[u] = cycles[id].size();
            cycles[id].push_back(u);
            root[u] = u;
            u = f[u];
        } while (u != v);
    }
    // Reverse Kahn order: f[u] is always finished before u.
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        root[u] = root[f[u]];
        depth[u] = depth[f[u]] + 1;
        cycId[u] = cycId[root[u]];
    }
    for (int v = 1; v <= n; v++)
        cout << depth[v] + cycles[cycId[v]].size() << " \n"[v == n];
}

Tìm chu trình bằng tô màu 3 trạng thái (không đệ quy)

Đoạn dưới đây không có main: đặt nó ngay sau phần đọc $n$ và $f (1 . . n)$ trong chương trình phân rã ở trên (thay cho phần xóa đỉnh bậc vào 0). Sau vòng lặp, onCycle[v] = 1 đúng với các đỉnh nằm trên chu trình.

// color: 0 = unvisited, 1 = on the current path, 2 = done
vector<int> color(n + 1, 0), onCycle(n + 1, 0);
for (int s = 1; s <= n; s++) {
    if (color[s] != 0) continue;
    vector<int> path;
    int v = s;
    while (color[v] == 0) {           // walk until we hit something already seen
        color[v] = 1;
        path.push_back(v);
        v = f[v];
    }
    if (color[v] == 1) {              // hit our own path: a brand new cycle
        int u = v;
        do { onCycle[u] = 1; u = f[u]; } while (u != v);
    }
    for (int u : path) color[u] = 2;  // color 2 => no new cycle through here
}

Floyd rùa và thỏ

Đây là một hàm độc lập: đặt nó phía trên main của chương trình phân rã (sau using namespace std;), rồi trong main, sau khi đọc $n$ và $f$ , gọi auto [mu, lambda] = floydCycle(1, f);.

// Returns {mu, lambda}: tail length and cycle length of x0, f(x0), f(f(x0)), ...
pair<long long, long long> floydCycle(int x0, const vector<int>& f) {
    int tortoise = f[x0], hare = f[f[x0]];
    while (tortoise != hare) {        // phase 1: meet somewhere on the cycle
        tortoise = f[tortoise];
        hare = f[f[hare]];
    }
    long long mu = 0;
    tortoise = x0;                    // phase 2: restart tortoise from x0
    while (tortoise != hare) {
        tortoise = f[tortoise];
        hare = f[hare];
        mu++;
    }
    long long lambda = 1;             // phase 3: walk the cycle once
    int hare2 = f[tortoise];
    while (tortoise != hare2) {
        hare2 = f[hare2];
        lambda++;
    }
    return {mu, lambda};
}

Trong bài thật, $f$ thường là một hàm tính toán (ví dụ bộ sinh số giả ngẫu nhiên) chứ không phải mảng; chỉ cần thay f[x] bằng lời gọi hàm.

Đi đúng $k$ bước, $k \leq 10^{18}$ (binary lifting)

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

const int LOG = 60;                    // 2^60 > 1e18; use 30 if k <= 1e9

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    // up[j][v] = vertex reached from v after exactly 2^j steps
    vector<vector<int>> up(LOG, vector<int>(n + 1));
    for (int v = 1; v <= n; v++) cin >> up[0][v];
    for (int j = 1; j < LOG; j++)
        for (int v = 1; v <= n; v++)
            up[j][v] = up[j - 1][up[j - 1][v]];   // 2^j = 2^(j-1) + 2^(j-1)

    while (q--) {
        int v;
        long long k;
        cin >> v >> k;
        for (int j = 0; j < LOG; j++)
            if ((k >> j) & 1LL) v = up[j][v];      // take the 2^j jump if bit j is set
        cout << v << '\n';
    }
}

Mô phỏng trạng thái rồi tua nhanh

Khung chung cho mọi bài "hệ tất định chạy $T$ bước": mã hóa trạng thái thành số nguyên trong $[0, S)$ , viết hàm nextState.

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

const int S = 10;                                    // number of possible states
int nextState(int x) { return (x * x + 1) % 10; }    // deterministic transition

int main() {
    int s = 3;
    long long T = 100;
    vector<long long> seen(S, -1);   // seen[x] = first time state x appeared
    long long t = 0, remaining = T;
    bool jumped = false;
    while (remaining > 0) {
        if (!jumped && seen[s] != -1) {
            long long cycleLen = t - seen[s];
            remaining %= cycleLen;   // skip whole laps of the cycle, only once
            jumped = true;
            if (remaining == 0) break;
        }
        seen[s] = t;
        s = nextState(s);
        t++;
        remaining--;
    }
    cout << s << '\n';               // prints 5
}

Với robot trên lưới, trạng thái là $(x, y, hướng)$ , mã hóa thành $((x \cdot W) + y) \cdot 4 + hướng$ .

Python: tìm chu trình và độ sâu

from collections import deque
import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    f = [0] + [int(x) for x in data[1:1 + n]]

    indeg = [0] * (n + 1)
    for v in range(1, n + 1):
        indeg[f[v]] += 1
    q = deque(v for v in range(1, n + 1) if indeg[v] == 0)
    order = []
    while q:                      # peel off tree vertices
        u = q.popleft()
        order.append(u)
        indeg[f[u]] -= 1
        if indeg[f[u]] == 0:
            q.append(f[u])

    on_cycle = [indeg[v] > 0 for v in range(n + 1)]
    depth = [0] * (n + 1)
    for u in reversed(order):     # f[u] is finished before u
        depth[u] = depth[f[u]] + 1
    print(sum(on_cycle), max(depth))

main()

Độ phức tạp

Thao tác	Thời gian	Bộ nhớ	Lý do
Xóa đỉnh bậc vào 0 + phân rã	$O (N)$	$O (N)$	Mỗi đỉnh vào hàng đợi tối đa một lần, mỗi cạnh làm giảm bậc vào đúng một lần; đi vòng mỗi chu trình một lần.
Tô màu 3 trạng thái	$O (N)$	$O (N)$	Mỗi đỉnh được tô màu 1 đúng một lần; vòng liệt kê chu trình chỉ chạy trên chu trình mới, tổng cộng $\leq N$ .
Floyd	$O (μ + λ)$	$O (1)$	Pha 1 kết thúc sau $\leq μ + λ$ lượt, pha 2 đúng $μ$ bước, pha 3 đúng $λ$ bước.
Binary lifting	$O (N \log K)$ dựng, $O (\log K)$ mỗi truy vấn	$O (N \log K)$	Bảng có $\log_{2} K$ tầng, mỗi ô tính $O (1)$ từ tầng dưới; truy vấn duyệt từng bit của $k$ .
Mô phỏng + chia lấy dư	$O (S)$	$O (S)$	Trước khi lặp có không quá $S$ bước, sau khi lấy dư còn $< λ \leq S$ bước.

Lưu ý bộ nhớ của binary lifting: với $N = 2 \cdot 10^{5}$ và $\log K = 60$ , bảng int chiếm $2 \cdot 10^{5} \cdot 60 \cdot 4 \approx 48$ MB. Nếu giới hạn bộ nhớ chặt, dùng phân rã ở trên: với $k \geq d e p t h [v]$ , đi tới gốc rồi tính vị trí trên chu trình bằng $(p o s [r o o t] + k - d e p t h [v]) mod | chu trình |$ trong $O (1)$ ; chỉ phần $k < d e p t h [v]$ (đi trên cây) mới cần nhảy. Phần đi trên cây này vẫn dùng bảng binary lifting, nhưng vì $k < d e p t h [v] < N$ nên chỉ cần khoảng $\log_{2} N \approx 18$ tầng thay vì khoảng 60 tầng, tức bộ nhớ bảng giảm từ khoảng 48 MB xuống khoảng $2 \cdot 10^{5} \cdot 18 \cdot 4 \approx 14$ MB.

⚠️ Lỗi thường gặp

DFS đệ quy bị tràn stack. Đồ thị hàm có thể là một đường dài $2 \cdot 10^{5}$ đỉnh đổ vào một chu trình nhỏ. DFS đệ quy sâu như vậy dễ gây Runtime Error. Cách tránh: dùng vòng while đi theo $f$ như code tô màu ở trên, hoặc dùng cách xóa đỉnh bậc vào 0.
Coi chạm đỉnh màu 2 là tìm thấy chu trình. Chạm đỉnh đã xử lý xong (màu 2) chỉ có nghĩa là đường hiện tại đổ vào phần đã biết. Chỉ khi chạm đỉnh màu 1 (trên chính đường đang đi) mới có chu trình mới. Nhầm hai trường hợp sẽ đếm một chu trình nhiều lần hoặc đánh dấu đỉnh trên cây là đỉnh chu trình.
Tràn số hoặc thiếu tầng khi $k$ tới $10^{18}$ . Đọc $k$ bằng long long, dùng (k >> j) & 1LL và LOG = 60. Viết 1 << j với int sẽ sai khi $j \geq 31$ ; để LOG = 30 với $k = 10^{18}$ sẽ bỏ sót các bit cao và cho đáp án sai mà không báo lỗi.
Mô phỏng thiếu thành phần của trạng thái. Chu trình chỉ tồn tại trên trạng thái đầy đủ. Robot đi qua cùng một ô theo hai hướng khác nhau là hai trạng thái khác nhau; nếu chỉ lưu ô, ta "phát hiện chu trình" giả và tua sai. Tự hỏi: biết giá trị này có đủ để suy ra toàn bộ tương lai không?
Off-by-one khi tua nhanh. Độ dài chu trình là $t_{hiện tại} - s e e n [s]$ , trong đó $s e e n [s]$ là lần gặp đầu tiên. Phải trừ đi số bước đã đi (phần đuôi) trước khi lấy dư; lấy $T mod λ$ ngay từ đầu là sai khi $μ > 0$ . Chỉ lấy dư một lần, sau đó đi tiếp phần dư bình thường.
Floyd pha 2 đưa nhầm con trỏ về đầu. Phải đưa rùa về $x_{0}$ và giữ thỏ tại điểm gặp, rồi cả hai cùng đi 1 bước. Cho thỏ tiếp tục đi 2 bước ở pha 2 sẽ làm vòng lặp không dừng hoặc ra $μ$ sai.
Quên các trường hợp đặc biệt. Khuyên tự lặp $f (v) = v$ là chu trình độ dài 1; đồ thị có thể có nhiều thành phần; khi $f$ là hoán vị thì không có đuôi, mọi đỉnh đều trên chu trình. Code phải chạy đúng cả ba trường hợp này.

Biến thể / Mở rộng

Hoán vị là đồ thị hàm đặc biệt: mọi đỉnh có bậc vào bằng 1, nên đồ thị chỉ gồm các chu trình rời nhau. Nhiều bài "áp dụng hoán vị $K$ lần" giải bằng cách tách chu trình rồi dịch vị trí đi $K mod$ độ dài chu trình.
Khoảng cách từ $a$ tới $b$ : dùng phân rã. Nếu $b$ trên chu trình: $a$ phải đổ vào cùng chu trình, đáp án $= d e p t h [a]$ cộng khoảng cách trên vòng từ $r o o t [a]$ tới $b$ . Nếu $b$ trên cây: $b$ phải là "tổ tiên" của $a$ trên cùng cây, kiểm tra bằng $r o o t$ , $d e p t h$ và nhảy $d e p t h [a] - d e p t h [b]$ bước.
Kèm giá trị trên đường đi: lưu thêm $s u m [j] [v]$ hoặc $m n [j] [v]$ cạnh bảng $u p$ để lấy tổng/min trên $k$ bước, y như binary lifting trên cây.
Thuật toán Brent: một cách khác dùng $O (1)$ bộ nhớ, thường gọi $f$ ít hơn Floyd, trực tiếp cho $λ$ trước rồi mới tìm $μ$ .
Liên hệ: các chu trình của đồ thị hàm chính là các thành phần liên thông mạnh có nhiều hơn một đỉnh (hoặc có khuyên), xem Thành phần liên thông mạnh. Phần cây treo vào chu trình thường được xử lý bằng BFS trên cạnh ngược, và nhảy $k$ bước trên cây là Binary Lifting.

Bài tập luyện

Luyện kỹ thuật

Chu Trình Hành Tinh (planetcyc) (Trung cấp) Với mỗi đỉnh xuất phát, số bước tới khi gặp lại đỉnh cũ bằng độ sâu tới chu trình cộng độ dài chu trình; bài khởi động cho phân rã đuôi và chu trình.
Hành Tinh (Truy vấn I) (planetsq1) (Trung cấp) Đi đúng $k \leq 10^{9}$ bước từ $x$ : bài binary lifting trên đồ thị hàm kinh điển nhất.
Xáo Bài Bessie (shuffle) (Trung cấp) Truy ngược vị trí qua các vòng xáo: vị trí $p$ trong cửa sổ ở vòng sau lấy lá từ vị trí nào ở vòng trước; ánh xạ ngược này là một đồ thị hàm có điểm cố định (vị trí lá mới rút vào), nên nhảy nhiều vòng bằng binary lifting.
Hành Tinh (Truy vấn II) (planetsq2) (Nâng cao) Khoảng cách tối thiểu từ $a$ tới $b$ : cần đủ bộ gốc, độ sâu, vị trí trên chu trình và phân loại $a$ , $b$ nằm trên cây hay trên chu trình.
The Chase (thechase) (Kỳ cựu) Phân rã từng thành phần thành đuôi và chu trình, lan thời điểm nông dân tới sớm nhất theo $f$ (theo thứ tự bóc lá rồi đi hai vòng quanh chu trình), rồi so độ lệch (vị trí trên chu trình trừ độ sâu) theo modulo độ dài chu trình để biết được nghỉ bao nhiêu lần; nếu không nông dân nào từng tới đỉnh xuất phát thì Bessie đứng yên mãi.

Đề VOI

Robot (voi18_robot) (Nâng cao) VOI 2018: trạng thái (ô, hướng) trong hình vuông bao quanh mê cung là hữu hạn, nên mô phỏng, ghi thời điểm gặp mỗi trạng thái rồi rút gọn thời gian còn lại (số giây trong đề) bằng chia lấy dư theo độ dài chu trình; khi robot ra khỏi vùng đó thì nó đi thẳng mãi.
Chia nhóm (voi21_teamup) (Chuyên gia) VOI 2021: các cạnh $i \to p_{i}$ tạo thành đồ thị hàm, nên mỗi thành phần có đúng một chu trình (chỉ chu trình lẻ gây tốn kém); để xử lý cạnh giả định thêm vào cần gốc trên chu trình, độ sâu và binary lifting kèm min trên các cây treo.

Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.