Functional Graph (ダブリングK回行動)
(src/graph/Functional-Graph.hpp)

• View this file on GitHub
• Last update: 2022-11-08 10:32:07+09:00
• Include: #include "src/graph/Functional-Graph.hpp"

概要

zawa::Functional_Graph<std::size_t log = 64> (const std::vector<int>& as)

Functional Graph を扱います。

Functional Graphとは

$N$ 頂点 $N$ 辺で自己ループを持たない有向グラフ。どの辺も出次数が1である。

機能

• コンストラクタ: 各頂点について伸びている辺の向かう先を保存したstd::vector<int>の参照をとります
• inline int f(int x): xから出る辺の行く先を返します
• int walk(int start, long long step): 頂点startからstep回辺を辿って移動することを繰り返した後にいる頂点を返します。
• std::tuple<int, int, int> detect(int start): 頂点startを含むグラフの連結成分からサイクルを検出します。返り値のstd::tupleの中身はそれぞれ「startから移動を開始してサイクルに入るまでの最小移動回数」「startから移動を開始して最初に辿り着くサイクルの頂点」「サイクルの頂点数」です

計算量

• コンストラクタ: $O(N\log N)$
• f: $O(1)$
• walk: $O(\log N)$
• detect: $O(N)$

メモ

ダブリングしゅごい

TODO?

• あらかじめ連結成分に分解する -> detectを高速にする

Verified with

• test/Functional_Graph.test.cpp

Code

#pragma once

#include <vector>
#include <tuple>

namespace zawa {

template <std::size_t log = 63>
class Functional_Graph {
private:
    std::vector<int> fs;
    std::vector<std::vector<int>> table;

public:
    Functional_Graph(const std::vector<int>& as)
        : fs(as.begin(), as.end())
        , table(log, std::vector(as.size(), -1)) {
        table[0] = as;
        for (std::size_t i = 0 ; i + 1 < 63 ; i++) {
            for (std::size_t j = 0 ; j < fs.size() ; j++) {
                table[i + 1][j] = table[i][table[i][j]];
            }
        }
    }

    inline int f(int x) {
        return fs[x];
    }

    int walk(int start, long long step) {
        int res = start;
        for (std::size_t i = 0 ; i < log ; i++) {
            if (step & 1) {
                res = table[i][res];
            }
            step >>= 1;
        }
        return res;
    }

    std::tuple<int, int, int> detect(int start) {
        std::vector used(fs.size(), -1);
        int step = 0;
        int now = start;
        for ( ; ; step++) {
            if (~used[now]) {
                break;
            }
            used[now] = step;
            now = f(now);
        }
        return std::tuple(used[now], now, step - used[now]);
    }

};

}// namespace zawa

#line 2 "src/graph/Functional-Graph.hpp"

#include <vector>
#include <tuple>

namespace zawa {

template <std::size_t log = 63>
class Functional_Graph {
private:
    std::vector<int> fs;
    std::vector<std::vector<int>> table;

public:
    Functional_Graph(const std::vector<int>& as)
        : fs(as.begin(), as.end())
        , table(log, std::vector(as.size(), -1)) {
        table[0] = as;
        for (std::size_t i = 0 ; i + 1 < 63 ; i++) {
            for (std::size_t j = 0 ; j < fs.size() ; j++) {
                table[i + 1][j] = table[i][table[i][j]];
            }
        }
    }

    inline int f(int x) {
        return fs[x];
    }

    int walk(int start, long long step) {
        int res = start;
        for (std::size_t i = 0 ; i < log ; i++) {
            if (step & 1) {
                res = table[i][res];
            }
            step >>= 1;
        }
        return res;
    }

    std::tuple<int, int, int> detect(int start) {
        std::vector used(fs.size(), -1);
        int step = 0;
        int now = start;
        for ( ; ; step++) {
            if (~used[now]) {
                break;
            }
            used[now] = step;
            now = f(now);
        }
        return std::tuple(used[now], now, step - used[now]);
    }

};

}// namespace zawa

Back to top page