graph/namori.hpp

• View this file on GitHub
• Last update: 2023-11-04 18:06:00+09:00
• Include: #include "graph/namori.hpp"

Depends on

• グラフ構造体 (graph/graph_template.hpp)

Code

#pragma once

#include "graph_template.hpp"

template <typename Cost> class Namori : public Graph<Cost> {
  public:
    using Graph<Cost>::Graph;
    using Graph<Cost>::G;

    void build() {
        int N = (int)G.size();
        std::vector<int> deg(N), st;
        std::vector<bool> seen(N);
        for(int i = 0; i < N; i++) {
            deg[i] = (int)G[i].size();
            if(deg[i] == 1) {
                st.emplace_back(i);
                seen[i] = true;
            }
        }
        while(!st.empty()) {
            int u = st.back();
            st.pop_back();
            for(int v : G[u]) {
                if(seen[v]) continue;
                deg[v]--;
                if(deg[v] == 1) {
                    st.emplace_back(v);
                    seen[v] = true;
                }
            }
        }
        loop_id.resize(N, -1);
        std::vector<int> loop;
        for(int i = 0; i < N; i++) {
            if(seen[i]) continue;
            auto dfs = [&](auto &&self, int u) -> void {
                loop_id[u] = (int)loop.size();
                loop.push_back(u);
                seen[u] = true;
                for(int v : G[u]) {
                    if(seen[v]) continue;
                    self(self, v);
                }
            };
            dfs(dfs, i);
            break;
        }
        for(int i = 0; i < (int)loop.size(); i++) {
            auto dfs = [&](auto&& self, int u) -> void {
                for(int v : G[u]) {
                    if(loop_id[v] != -1) continue;
                    loop_id[v] = loop_id[u];
                    self(self, v);
                }
            };
            dfs(dfs, loop[i]);
        }
    }
    int operator[](int i) const { return loop_id[i]; }

  private:
    std::vector<int> loop_id;
};

#line 2 "graph/namori.hpp"

#line 2 "graph/graph_template.hpp"

#include <cassert>
#include <vector>

template <typename Cost = int> struct Edge {
    int from, to;
    Cost cost;
    int id;
    Edge() = default;
    explicit Edge(int from, int to, Cost cost = 1, int id = -1)
        : from(from), to(to), cost(cost), id(id) {}
    operator int() const { return to; }
};

template <typename Cost = int> class Graph {
  public:
    Graph() = default;
    explicit Graph(int N) : N(N), M(0), G(N) {}

    inline void add_directed_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M++);
    }

    inline void add_undirected_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M);
        G[to].emplace_back(to, from, cost, M++);
    }

    inline size_t size() const { return G.size(); }
    inline std::vector<Edge<Cost>> &operator[](const int &i) { return G[i]; }
    inline const std::vector<Edge<Cost>> &operator[](const int &i) const {
        return G[i];
    }

  protected:
    int N, M;
    std::vector<std::vector<Edge<Cost>>> G;
};

template <class Cost = int> using Edges = std::vector<Edge<Cost>>;
#line 4 "graph/namori.hpp"

template <typename Cost> class Namori : public Graph<Cost> {
  public:
    using Graph<Cost>::Graph;
    using Graph<Cost>::G;

    void build() {
        int N = (int)G.size();
        std::vector<int> deg(N), st;
        std::vector<bool> seen(N);
        for(int i = 0; i < N; i++) {
            deg[i] = (int)G[i].size();
            if(deg[i] == 1) {
                st.emplace_back(i);
                seen[i] = true;
            }
        }
        while(!st.empty()) {
            int u = st.back();
            st.pop_back();
            for(int v : G[u]) {
                if(seen[v]) continue;
                deg[v]--;
                if(deg[v] == 1) {
                    st.emplace_back(v);
                    seen[v] = true;
                }
            }
        }
        loop_id.resize(N, -1);
        std::vector<int> loop;
        for(int i = 0; i < N; i++) {
            if(seen[i]) continue;
            auto dfs = [&](auto &&self, int u) -> void {
                loop_id[u] = (int)loop.size();
                loop.push_back(u);
                seen[u] = true;
                for(int v : G[u]) {
                    if(seen[v]) continue;
                    self(self, v);
                }
            };
            dfs(dfs, i);
            break;
        }
        for(int i = 0; i < (int)loop.size(); i++) {
            auto dfs = [&](auto&& self, int u) -> void {
                for(int v : G[u]) {
                    if(loop_id[v] != -1) continue;
                    loop_id[v] = loop_id[u];
                    self(self, v);
                }
            };
            dfs(dfs, loop[i]);
        }
    }
    int operator[](int i) const { return loop_id[i]; }

  private:
    std::vector<int> loop_id;
};

Back to top page