Functional Graph

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Floyd's cycle-finding algorithm for a functional graph
5
// next[v] is the successor of v, 0 <= v < n
6
// Given start, computes (mu, lambda), where mu is the index of first cycle node
7
// along the orbit starting from start, and lambda is the cycle length.
8
struct CycleInfo {
9
    int mu;      // steps before entering the cycle
10
    int lambda;  // cycle length
11
    int cycleStartNode; // one node on the cycle (the entrance node)
12
};
13
14
CycleInfo floyd_cycle(const vector<int>& next, int start) {
15
    // 1) Phase 1: find meeting point inside the cycle (if any)
16
    int tortoise = next[start];            // f(x0)
17
    int hare = next[next[start]];          // f(f(x0))
18
    while (tortoise != hare) {
19
        tortoise = next[tortoise];
20
        hare = next[next[hare]];
21
    }
22
23
    // 2) Phase 2: find mu (cycle entrance index)
24
    int mu = 0;
25
    tortoise = start;                      // reset tortoise to start
26
    while (tortoise != hare) {
27
        tortoise = next[tortoise];
28
        hare = next[hare];
29
        ++mu;
30
    }
31
32
    // 3) Phase 3: find lambda (cycle length)
33
    int lambda = 1;
34
    hare = next[tortoise];
35
    while (tortoise != hare) {
36
        hare = next[hare];
37
        ++lambda;
38
    }
39
40
    return {mu, lambda, tortoise}; // tortoise is at the cycle entrance node
41
}
42
43
int main() {
44
    // Example functional graph on nodes [0..7]
45
    // 0->1->2->3->1 (cycle 1-2-3), 4->5->6->4 (cycle 4-5-6), 7->6
46
    vector<int> next = {1,2,3,1,5,6,4,6};
47
48
    int start = 0;
49
    CycleInfo info = floyd_cycle(next, start);
50
51
    cout << "Start: " << start << "\n";
52
    cout << "mu (steps to enter cycle): " << info.mu << "\n";
53
    cout << "lambda (cycle length): " << info.lambda << "\n";
54
    cout << "one cycle entrance node: " << info.cycleStartNode << "\n";
55
56
    // Demonstrate orbit until first repeat
57
    int v = start;
58
    cout << "Orbit: ";
59
    for (int i = 0; i < info.mu + info.lambda + 2; ++i) {
60
        cout << v << (i+1 < info.mu + info.lambda + 2 ? ' ' : '\n');
61
        v = next[v];
62
    }
63
    return 0;
64
}
65

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Decompose a functional graph into cycles and tails.
5
// For each node v, compute:
6
//  - comp_id[v]: which cycle component it belongs to (0..C-1)
7
//  - dist_to_cycle[v]: steps to reach the cycle (0 if v is on a cycle)
8
//  - pos_in_cycle[v]: position in the cycle (0..len-1) if on cycle, else -1
9
// This is done iteratively to avoid recursion stack issues.
10
11
struct Decomp {
12
    vector<int> comp_id;       // component (cycle) id per node
13
    vector<int> dist_to_cycle; // distance to cycle per node
14
    vector<int> pos_in_cycle;  // position in cycle or -1
15
    vector<int> cycle_len;     // length for each component id
16
};
17
18
Decomp decompose_functional_graph(const vector<int>& next) {
19
    int n = (int)next.size();
20
    vector<int> state(n, 0); // 0=unvisited, 1=visiting, 2=done
21
    vector<int> comp_id(n, -1), dist(n, 0), pos(n, -1);
22
    vector<int> cycle_len; // indexed by component id
23
24
    vector<int> stk; stk.reserve(n);
25
26
    int cid = 0;
27
    for (int s = 0; s < n; ++s) if (state[s] == 0) {
28
        int v = s;
29
        // Walk until we hit a visited node
30
        while (state[v] == 0) {
31
            state[v] = 1; // visiting
32
            stk.push_back(v);
33
            v = next[v];
34
        }
35
36
        if (state[v] == 1) {
37
            // Found a new cycle: extract nodes from stack until we reach v
38
            vector<int> cyc;
39
            while (true) {
40
                int u = stk.back(); stk.pop_back();
41
                cyc.push_back(u);
42
                if (u == v) break;
43
            }
44
            reverse(cyc.begin(), cyc.end());
45
46
            // Assign cycle nodes
47
            int L = (int)cyc.size();
48
            for (int i = 0; i < L; ++i) {
49
                int u = cyc[i];
50
                comp_id[u] = cid;
51
                pos[u] = i;         // position in cycle
52
                dist[u] = 0;        // on cycle
53
                state[u] = 2;       // done
54
            }
55
            cycle_len.push_back(L);
56
            ++cid;
57
        }
58
59
        // Propagate information back along the remaining stack (tail nodes)
60
        while (!stk.empty()) {
61
            int u = stk.back(); stk.pop_back();
62
            int w = next[u];
63
            comp_id[u] = comp_id[w];
64
            pos[u] = -1; // not on the cycle
65
            dist[u] = dist[w] + 1;
66
            state[u] = 2;
67
        }
68
    }
69
70
    return {comp_id, dist, pos, cycle_len};
71
}
72
73
int main() {
74
    // Example graph: 0->1->2->3->1, 4->5->6->4, 7->6
75
    vector<int> next = {1,2,3,1,5,6,4,6};
76
77
    Decomp D = decompose_functional_graph(next);
78
79
    int n = (int)next.size();
80
    cout << "node comp dist pos\n";
81
    for (int v = 0; v < n; ++v) {
82
        cout << v << ' ' << D.comp_id[v] << ' ' << D.dist_to_cycle[v] << ' ' << D.pos_in_cycle[v] << '\n';
83
    }
84
85
    cout << "\nCycle lengths per component id:\n";
86
    for (int c = 0; c < (int)D.cycle_len.size(); ++c) {
87
        cout << "comp " << c << ": length = " << D.cycle_len[c] << '\n';
88
    }
89
}
90

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Precompute jump pointers up[j][v] = 2^j-th successor of v
5
// and answer queries of the form: given (v, k), compute f^{(k)}(v).
6
7
struct JumpTable {
8
    int n;
9
    int LOG; // number of levels (e.g., 60 for k up to 1e18)
10
    vector<vector<int>> up; // up[j][v]
11
};
12
13
JumpTable build_jump_table(const vector<int>& next, int LOG) {
14
    int n = (int)next.size();
15
    vector<vector<int>> up(LOG, vector<int>(n));
16
    // Base: 2^0-th successor is the immediate successor
17
    for (int v = 0; v < n; ++v) up[0][v] = next[v];
18
    // Doubling
19
    for (int j = 1; j < LOG; ++j) {
20
        for (int v = 0; v < n; ++v) {
21
            up[j][v] = up[j-1][ up[j-1][v] ];
22
        }
23
    }
24
    return {n, LOG, move(up)};
25
}
26
27
int kth_successor(const JumpTable& JT, int v, unsigned long long k) {
28
    for (int j = 0; j < JT.LOG; ++j) {
29
        if (k & (1ULL << j)) v = JT.up[j][v];
30
    }
31
    return v;
32
}
33
34
int main() {
35
    ios::sync_with_stdio(false);
36
    cin.tie(nullptr);
37
38
    // Example graph: 0->1->2->3->1, 4->5->6->4, 7->6
39
    vector<int> next = {1,2,3,1,5,6,4,6};
40
41
    // Suppose k can be up to 1e18, choose LOG=60
42
    const int LOG = 60;
43
    JumpTable JT = build_jump_table(next, LOG);
44
45
    // Example queries
46
    vector<pair<int, unsigned long long>> queries = {
47
        {0, 0}, {0, 1}, {0, 2}, {0, 5}, // move from node 0 by k steps
48
        {7, 1}, {7, 2}, {7, 10}         // move from node 7 by k steps
49
    };
50
51
    for (auto [v, k] : queries) {
52
        int u = kth_successor(JT, v, k);
53
        cout << "k-th successor: from " << v << " by k=" << k << " => " << u << '\n';
54
    }
55
56
    return 0;
57
}
58