Functional Graph
(src/graph/FunctionalGraph.hpp)

• View this file on GitHub
• Last update: 2023-10-01 16:26:05+09:00
• Include: #include "src/graph/FunctionalGraph.hpp"

概要

Functional Graph とは各頂点の出次数が丁度 $1$ であるような有向グラフのことを指す． グラフはいくつかのループをもち，全体として各ループを根とするような森となる． visit[v] は $v$ が $i$ (0-indexed) 番目のループ上にあるなら $i + 1$，ループ上になく $i$ 番目のループにたどり着く場合には $- (i + 1)$ を格納する． G はループ上の頂点から葉へ向かう逆方向の森である．

問題例

• AtCoder Beginner Contest 296 E - Transition Game

Code

#pragma once
#include <cassert>
#include <vector>

struct FunctionalGraph {
    int n, L;
    std::vector<int> visit;
    std::vector<std::vector<int>> loops, G;

    FunctionalGraph(int n) : n(n), L(1), visit(n), G(n), nxt(n, -1) {}

    void add_edge(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        nxt[u] = v;
    }

    void build() {
        for (int i = 0; i < n; i++) {
            if (visit[i] != 0) continue;
            std::vector<int> loop;
            dfs(i, loop);
            if (not loop.empty()) loops.emplace_back(loop);
        }
        for (int i = 0; i < n; i++) {
            if (visit[i] < 0) {
                G[nxt[i]].emplace_back(i);
            }
        }
    }

  private:
    std::vector<int> nxt;

    void make_loop(int s, std::vector<int>& loop) {
        loop.emplace_back(s);
        visit[s] = L;
        for (int cur = nxt[s]; cur != s; cur = nxt[cur]) {
            loop.emplace_back(cur);
            visit[cur] = L;
        }
    }

    int dfs(int v, std::vector<int>& loop) {
        visit[v] = -L;
        int u = nxt[v];
        if (visit[u] == -L) {
            make_loop(v, loop);
            L++;
            return 0;
        } else if (visit[u] == 0) {
            int res = dfs(u, loop);
            if (res == 0) return 0;
            return visit[v] = res;
        }
        return visit[v] = (visit[u] > 0 ? -visit[u] : visit[u]);
    }
};

#line 2 "src/graph/FunctionalGraph.hpp"
#include <cassert>
#include <vector>

struct FunctionalGraph {
    int n, L;
    std::vector<int> visit;
    std::vector<std::vector<int>> loops, G;

    FunctionalGraph(int n) : n(n), L(1), visit(n), G(n), nxt(n, -1) {}

    void add_edge(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        nxt[u] = v;
    }

    void build() {
        for (int i = 0; i < n; i++) {
            if (visit[i] != 0) continue;
            std::vector<int> loop;
            dfs(i, loop);
            if (not loop.empty()) loops.emplace_back(loop);
        }
        for (int i = 0; i < n; i++) {
            if (visit[i] < 0) {
                G[nxt[i]].emplace_back(i);
            }
        }
    }

  private:
    std::vector<int> nxt;

    void make_loop(int s, std::vector<int>& loop) {
        loop.emplace_back(s);
        visit[s] = L;
        for (int cur = nxt[s]; cur != s; cur = nxt[cur]) {
            loop.emplace_back(cur);
            visit[cur] = L;
        }
    }

    int dfs(int v, std::vector<int>& loop) {
        visit[v] = -L;
        int u = nxt[v];
        if (visit[u] == -L) {
            make_loop(v, loop);
            L++;
            return 0;
        } else if (visit[u] == 0) {
            int res = dfs(u, loop);
            if (res == 0) return 0;
            return visit[v] = res;
        }
        return visit[v] = (visit[u] > 0 ? -visit[u] : visit[u]);
    }
};

Back to top page