m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Namori Graph Decomposition
(graph/namori.hpp)

Overview

namori_decomposition(graph) decomposes an undirected Namori graph: every connected component must contain exactly one cycle. It restores each cycle in order and roots every attached tree at the cycle vertex where it connects.

The algorithm repeatedly removes vertices of degree at most one. The remaining 2-core is the collection of cycles. It then traverses those cycles and grows the attached forest outward.

Parallel edges are supported and form a cycle of length two. A self-loop forms a cycle of length one. Inactive edges are ignored.

If any connected component is a tree or contains more than one cycle, the function returns std::nullopt.

Result

NamoriDecomposition<T> contains:

Field Meaning
component_count Number of connected components and cycles.
cycles[c] Cycle vertices of component c in cyclic order.
cycle_edge_ids[c] Edge from cycles[c][i] to the next cycle vertex, wrapping around.
cycle_edge_costs[c] Costs aligned with cycle_edge_ids[c].
on_cycle[v] Whether v lies on its component’s cycle.
component[v] Component and cycle id containing v.
cycle_root[v] Cycle vertex at the root of v’s attached tree.
cycle_position[v] Position of cycle_root[v] in cycles[component[v]].
parent[v] Parent toward the cycle, or -1 for cycle vertices.
parent_edge[v] Edge to parent[v], or -1 for cycle vertices.
depth[v] Number of tree edges from v to the cycle.
dist_to_cycle[v] Weighted distance from v to the cycle.
children[v] Children directed away from the cycle.

same_component(u, v) tests ordinary graph connectivity. same_tree(u, v) tests whether the vertices attach to the same cycle vertex.

Functions

Function Description Complexity
namori_decomposition(graph) Returns the decomposition, or nullopt for a non-Namori component. O(N + M)
decompose_namori(graph) Alias for namori_decomposition. O(N + M)

The graph must be undirected and built with Graph::add_edge.

Example

#include "graph/graph.hpp"
#include "graph/namori.hpp"
#include <iostream>

int main() {
    m1une::graph::Graph<long long> graph(5);
    graph.add_edge(0, 1, 2);
    graph.add_edge(1, 2, 3);
    graph.add_edge(2, 0, 4);
    graph.add_edge(1, 3, 5);
    graph.add_edge(3, 4, 6);

    auto decomposition = m1une::graph::namori_decomposition(graph);
    if (!decomposition) return 0;

    std::cout << decomposition->cycle_root[4] << '\n';
    std::cout << decomposition->dist_to_cycle[4] << '\n';  // 11
}

Depends on

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_NAMORI_HPP
#define M1UNE_GRAPH_NAMORI_HPP 1

#include <cassert>
#include <optional>
#include <queue>
#include <utility>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

template <class T>
struct NamoriDecomposition {
    int component_count;
    std::vector<std::vector<int>> cycles;
    std::vector<std::vector<int>> cycle_edge_ids;
    std::vector<std::vector<T>> cycle_edge_costs;

    std::vector<bool> on_cycle;
    std::vector<int> component;
    std::vector<int> cycle_root;
    std::vector<int> cycle_position;
    std::vector<int> parent;
    std::vector<int> parent_edge;
    std::vector<int> depth;
    std::vector<T> dist_to_cycle;
    std::vector<std::vector<int>> children;

    bool same_component(int u, int v) const {
        assert(0 <= u && u < int(component.size()));
        assert(0 <= v && v < int(component.size()));
        return component[u] == component[v];
    }

    bool same_tree(int u, int v) const {
        assert(0 <= u && u < int(cycle_root.size()));
        assert(0 <= v && v < int(cycle_root.size()));
        return cycle_root[u] == cycle_root[v];
    }
};

template <class T>
std::optional<NamoriDecomposition<T>> namori_decomposition(const Graph<T>& graph) {
    int n = graph.size();
    NamoriDecomposition<T> result;
    result.component_count = 0;
    result.on_cycle.assign(n, false);
    result.component.assign(n, -1);
    result.cycle_root.assign(n, -1);
    result.cycle_position.assign(n, -1);
    result.parent.assign(n, -1);
    result.parent_edge.assign(n, -1);
    result.depth.assign(n, 0);
    result.dist_to_cycle.assign(n, T(0));
    result.children.assign(n, {});
    if (n == 0) return result;

    std::vector<int> degree(n, 0);
    for (int v = 0; v < n; v++) {
        for (const auto& edge : graph[v]) {
            if (edge.alive) degree[v]++;
        }
    }

    std::queue<int> queue;
    std::vector<bool> removed(n, false);
    for (int v = 0; v < n; v++) {
        if (degree[v] <= 1) queue.push(v);
    }
    while (!queue.empty()) {
        int v = queue.front();
        queue.pop();
        if (removed[v] || degree[v] > 1) continue;
        removed[v] = true;
        for (const auto& edge : graph[v]) {
            if (!edge.alive || removed[edge.to]) continue;
            degree[edge.to]--;
            if (degree[edge.to] == 1) queue.push(edge.to);
        }
    }

    for (int v = 0; v < n; v++) {
        result.on_cycle[v] = !removed[v];
    }
    for (int v = 0; v < n; v++) {
        if (!result.on_cycle[v]) continue;
        int cycle_degree = 0;
        for (const auto& edge : graph[v]) {
            if (edge.alive && result.on_cycle[edge.to]) cycle_degree++;
        }
        if (cycle_degree != 2) return std::nullopt;
    }

    std::vector<bool> cycle_visited(n, false);
    for (int start = 0; start < n; start++) {
        if (!result.on_cycle[start] || cycle_visited[start]) continue;
        int component_id = int(result.cycles.size());
        std::vector<int> vertices;
        std::vector<int> edge_ids;
        std::vector<T> edge_costs;

        int current = start;
        int previous_edge = -1;
        while (true) {
            if (cycle_visited[current]) return std::nullopt;
            cycle_visited[current] = true;
            vertices.push_back(current);

            int next_vertex = -1;
            int next_edge = -1;
            T next_cost = T(0);
            for (const auto& edge : graph[current]) {
                if (!edge.alive || !result.on_cycle[edge.to] || edge.id == previous_edge) continue;
                next_vertex = edge.to;
                next_edge = edge.id;
                next_cost = edge.cost;
                break;
            }
            if (next_edge == -1) return std::nullopt;
            edge_ids.push_back(next_edge);
            edge_costs.push_back(next_cost);
            if (next_vertex == start) break;
            previous_edge = next_edge;
            current = next_vertex;
            if (int(vertices.size()) > n) return std::nullopt;
        }

        for (int position = 0; position < int(vertices.size()); position++) {
            int v = vertices[position];
            result.component[v] = component_id;
            result.cycle_root[v] = v;
            result.cycle_position[v] = position;
        }
        result.cycles.push_back(std::move(vertices));
        result.cycle_edge_ids.push_back(std::move(edge_ids));
        result.cycle_edge_costs.push_back(std::move(edge_costs));
    }
    if (result.cycles.empty()) return std::nullopt;

    std::vector<int> stack;
    stack.reserve(n);
    for (const auto& cycle : result.cycles) {
        for (int v : cycle) stack.push_back(v);
    }
    while (!stack.empty()) {
        int v = stack.back();
        stack.pop_back();
        for (const auto& edge : graph[v]) {
            if (!edge.alive || result.on_cycle[edge.to] || edge.id == result.parent_edge[v]) continue;
            int to = edge.to;
            if (result.component[to] != -1) continue;
            result.component[to] = result.component[v];
            result.cycle_root[to] = result.cycle_root[v];
            result.cycle_position[to] = result.cycle_position[v];
            result.parent[to] = v;
            result.parent_edge[to] = edge.id;
            result.depth[to] = result.depth[v] + 1;
            result.dist_to_cycle[to] = result.dist_to_cycle[v] + edge.cost;
            result.children[v].push_back(to);
            stack.push_back(to);
        }
    }
    for (int v = 0; v < n; v++) {
        if (result.component[v] == -1) return std::nullopt;
    }

    result.component_count = int(result.cycles.size());
    return result;
}

template <class T>
std::optional<NamoriDecomposition<T>> decompose_namori(const Graph<T>& graph) {
    return namori_decomposition(graph);
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_NAMORI_HPP
#line 1 "graph/namori.hpp"



#include <cassert>
#include <optional>
#include <queue>
#include <utility>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 11 "graph/namori.hpp"

namespace m1une {
namespace graph {

template <class T>
struct NamoriDecomposition {
    int component_count;
    std::vector<std::vector<int>> cycles;
    std::vector<std::vector<int>> cycle_edge_ids;
    std::vector<std::vector<T>> cycle_edge_costs;

    std::vector<bool> on_cycle;
    std::vector<int> component;
    std::vector<int> cycle_root;
    std::vector<int> cycle_position;
    std::vector<int> parent;
    std::vector<int> parent_edge;
    std::vector<int> depth;
    std::vector<T> dist_to_cycle;
    std::vector<std::vector<int>> children;

    bool same_component(int u, int v) const {
        assert(0 <= u && u < int(component.size()));
        assert(0 <= v && v < int(component.size()));
        return component[u] == component[v];
    }

    bool same_tree(int u, int v) const {
        assert(0 <= u && u < int(cycle_root.size()));
        assert(0 <= v && v < int(cycle_root.size()));
        return cycle_root[u] == cycle_root[v];
    }
};

template <class T>
std::optional<NamoriDecomposition<T>> namori_decomposition(const Graph<T>& graph) {
    int n = graph.size();
    NamoriDecomposition<T> result;
    result.component_count = 0;
    result.on_cycle.assign(n, false);
    result.component.assign(n, -1);
    result.cycle_root.assign(n, -1);
    result.cycle_position.assign(n, -1);
    result.parent.assign(n, -1);
    result.parent_edge.assign(n, -1);
    result.depth.assign(n, 0);
    result.dist_to_cycle.assign(n, T(0));
    result.children.assign(n, {});
    if (n == 0) return result;

    std::vector<int> degree(n, 0);
    for (int v = 0; v < n; v++) {
        for (const auto& edge : graph[v]) {
            if (edge.alive) degree[v]++;
        }
    }

    std::queue<int> queue;
    std::vector<bool> removed(n, false);
    for (int v = 0; v < n; v++) {
        if (degree[v] <= 1) queue.push(v);
    }
    while (!queue.empty()) {
        int v = queue.front();
        queue.pop();
        if (removed[v] || degree[v] > 1) continue;
        removed[v] = true;
        for (const auto& edge : graph[v]) {
            if (!edge.alive || removed[edge.to]) continue;
            degree[edge.to]--;
            if (degree[edge.to] == 1) queue.push(edge.to);
        }
    }

    for (int v = 0; v < n; v++) {
        result.on_cycle[v] = !removed[v];
    }
    for (int v = 0; v < n; v++) {
        if (!result.on_cycle[v]) continue;
        int cycle_degree = 0;
        for (const auto& edge : graph[v]) {
            if (edge.alive && result.on_cycle[edge.to]) cycle_degree++;
        }
        if (cycle_degree != 2) return std::nullopt;
    }

    std::vector<bool> cycle_visited(n, false);
    for (int start = 0; start < n; start++) {
        if (!result.on_cycle[start] || cycle_visited[start]) continue;
        int component_id = int(result.cycles.size());
        std::vector<int> vertices;
        std::vector<int> edge_ids;
        std::vector<T> edge_costs;

        int current = start;
        int previous_edge = -1;
        while (true) {
            if (cycle_visited[current]) return std::nullopt;
            cycle_visited[current] = true;
            vertices.push_back(current);

            int next_vertex = -1;
            int next_edge = -1;
            T next_cost = T(0);
            for (const auto& edge : graph[current]) {
                if (!edge.alive || !result.on_cycle[edge.to] || edge.id == previous_edge) continue;
                next_vertex = edge.to;
                next_edge = edge.id;
                next_cost = edge.cost;
                break;
            }
            if (next_edge == -1) return std::nullopt;
            edge_ids.push_back(next_edge);
            edge_costs.push_back(next_cost);
            if (next_vertex == start) break;
            previous_edge = next_edge;
            current = next_vertex;
            if (int(vertices.size()) > n) return std::nullopt;
        }

        for (int position = 0; position < int(vertices.size()); position++) {
            int v = vertices[position];
            result.component[v] = component_id;
            result.cycle_root[v] = v;
            result.cycle_position[v] = position;
        }
        result.cycles.push_back(std::move(vertices));
        result.cycle_edge_ids.push_back(std::move(edge_ids));
        result.cycle_edge_costs.push_back(std::move(edge_costs));
    }
    if (result.cycles.empty()) return std::nullopt;

    std::vector<int> stack;
    stack.reserve(n);
    for (const auto& cycle : result.cycles) {
        for (int v : cycle) stack.push_back(v);
    }
    while (!stack.empty()) {
        int v = stack.back();
        stack.pop_back();
        for (const auto& edge : graph[v]) {
            if (!edge.alive || result.on_cycle[edge.to] || edge.id == result.parent_edge[v]) continue;
            int to = edge.to;
            if (result.component[to] != -1) continue;
            result.component[to] = result.component[v];
            result.cycle_root[to] = result.cycle_root[v];
            result.cycle_position[to] = result.cycle_position[v];
            result.parent[to] = v;
            result.parent_edge[to] = edge.id;
            result.depth[to] = result.depth[v] + 1;
            result.dist_to_cycle[to] = result.dist_to_cycle[v] + edge.cost;
            result.children[v].push_back(to);
            stack.push_back(to);
        }
    }
    for (int v = 0; v < n; v++) {
        if (result.component[v] == -1) return std::nullopt;
    }

    result.component_count = int(result.cycles.size());
    return result;
}

template <class T>
std::optional<NamoriDecomposition<T>> decompose_namori(const Graph<T>& graph) {
    return namori_decomposition(graph);
}

}  // namespace graph
}  // namespace m1une
Back to top page