#include "graph/functional-graph.hpp"
#pragma once #include <cassert> #include <utility> #include <vector> using namespace std; #include "../data-structure/union-find.hpp" #include "../internal/internal-type-traits.hpp" #include "graph-template.hpp" namespace FunctionalGraphImpl { ENABLE_HAS_VAR(cost) template <typename T = int> struct FunctionalGraph { int N; WeightedGraph<T> g; vector<int> to, represent; vector<T> weight; FunctionalGraph() = default; FunctionalGraph(int n, const vector<int>& adj, const vector<T>& w = vector<int>{}) : N(n), g(N + 1), to(N + 1, -1), represent(N + 1, -1), weight(N + 1) { assert((int)adj.size() == N); assert((int)w.size() == N or w.empty()); for (auto& x : adj) assert(0 <= x and x < N); UnionFind uf(N); for (int i = 0; i < N; i++) { int j = adj[i]; to[i] = j, weight[i] = w.empty() ? T{1} : w[i]; if (uf.same(i, j)) { g[N].emplace_back(N, i, weight[i]); } else { uf.unite(i, j); g[j].emplace_back(j, i, weight[i]); } } calc_represent(N, -1); } // _g は無向グラフ template <typename G> FunctionalGraph(int n, const G& _g) : N(n), g(N + 1), to(N + 1, -1), represent(N + 1, -1), weight(N + 1) { constexpr bool cost_flag = has_cost_v<typename G::value_type::value_type>; WeightedGraph<T> h(n); UnionFind uf(N); for (int i = 0; i < N; i++) { for (auto& j : _g[i]) { if (i > j) continue; T cost; if constexpr (cost_flag) { cost = j.cost; } else { cost = 1; } if (uf.same(i, j)) { // i -> j 向きということにして, i を根とする g[N].emplace_back(N, i, 0); to[i] = j, weight[i] = cost; } else { uf.unite(i, j); h[i].emplace_back(i, j, cost); h[j].emplace_back(j, i, cost); } } } auto dfs = [&](auto rc, int c, int p) -> void { for (auto& d : h[c]) { if (d == p) continue; T cost; if constexpr (cost_flag) { cost = d.cost; } else { cost = 1; } to[d] = c, weight[d] = cost; g[c].emplace_back(c, d, cost); rc(rc, d, c); } }; for (auto& r : g[N]) dfs(dfs, r, -1); calc_represent(N, -1); } vector<vector<int>> get_loops() const { vector<vector<int>> res; for (auto r : g[N]) { vector<int> cur{r}; for (int i = to[r]; i != r; i = to[i]) { cur.push_back(i); } res.push_back(cur); } return res; } // (u, {weight of u-v}) (v, {weight of v-w}), (w, ...) ... vector<vector<pair<int, T>>> get_loops_with_weight() const { vector<vector<pair<int, T>>> res; for (auto r : g[N]) { vector<pair<int, T>> cur{make_pair(r, weight[r])}; for (int i = to[r]; i != r; i = to[i]) { cur.emplace_back(i, weight[i]); } res.push_back(cur); } return res; } private: void calc_represent(int c, int r) { represent[c] = r; for (auto& d : g[c]) calc_represent(d, r == -1 ? d : r); } }; } // namespace FunctionalGraphImpl using FunctionalGraphImpl::FunctionalGraph;
#line 2 "graph/functional-graph.hpp" #include <cassert> #include <utility> #include <vector> using namespace std; #line 2 "data-structure/union-find.hpp" struct UnionFind { vector<int> data; UnionFind(int N) : data(N, -1) {} int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); } int unite(int x, int y) { if ((x = find(x)) == (y = find(y))) return false; if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return true; } // f ... merge function template<typename F> int unite(int x, int y,const F &f) { if ((x = find(x)) == (y = find(y))) return false; if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; f(x, y); return true; } int size(int k) { return -data[find(k)]; } int same(int x, int y) { return find(x) == find(y); } }; /** * @brief Union Find(Disjoint Set Union) * @docs docs/data-structure/union-find.md */ #line 2 "internal/internal-type-traits.hpp" #include <type_traits> using namespace std; namespace internal { template <typename T> using is_broadly_integral = typename conditional_t<is_integral_v<T> || is_same_v<T, __int128_t> || is_same_v<T, __uint128_t>, true_type, false_type>::type; template <typename T> using is_broadly_signed = typename conditional_t<is_signed_v<T> || is_same_v<T, __int128_t>, true_type, false_type>::type; template <typename T> using is_broadly_unsigned = typename conditional_t<is_unsigned_v<T> || is_same_v<T, __uint128_t>, true_type, false_type>::type; #define ENABLE_VALUE(x) \ template <typename T> \ constexpr bool x##_v = x<T>::value; ENABLE_VALUE(is_broadly_integral); ENABLE_VALUE(is_broadly_signed); ENABLE_VALUE(is_broadly_unsigned); #undef ENABLE_VALUE #define ENABLE_HAS_TYPE(var) \ template <class, class = void> \ struct has_##var : false_type {}; \ template <class T> \ struct has_##var<T, void_t<typename T::var>> : true_type {}; \ template <class T> \ constexpr auto has_##var##_v = has_##var<T>::value; #define ENABLE_HAS_VAR(var) \ template <class, class = void> \ struct has_##var : false_type {}; \ template <class T> \ struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \ template <class T> \ constexpr auto has_##var##_v = has_##var<T>::value; } // namespace internal #line 2 "graph/graph-template.hpp" template <typename T> struct edge { int src, to; T cost; edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {} edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template <typename T> using Edges = vector<edge<T>>; template <typename T> using WeightedGraph = vector<Edges<T>>; using UnweightedGraph = vector<vector<int>>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].push_back(y); if (!is_directed) g[y].push_back(x); } return g; } // Input of Weighted Graph template <typename T> WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph<T> g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].emplace_back(x, y, c); if (!is_directed) g[y].emplace_back(y, x, c); } return g; } // Input of Edges template <typename T> Edges<T> esgraph([[maybe_unused]] int N, int M, int is_weighted = true, bool is_1origin = true) { Edges<T> es; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; es.emplace_back(x, y, c); } return es; } // Input of Adjacency Matrix template <typename T> vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true, bool is_directed = false, bool is_1origin = true) { vector<vector<T>> d(N, vector<T>(N, INF)); for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; d[x][y] = c; if (!is_directed) d[y][x] = c; } return d; } /** * @brief グラフテンプレート * @docs docs/graph/graph-template.md */ #line 11 "graph/functional-graph.hpp" namespace FunctionalGraphImpl { ENABLE_HAS_VAR(cost) template <typename T = int> struct FunctionalGraph { int N; WeightedGraph<T> g; vector<int> to, represent; vector<T> weight; FunctionalGraph() = default; FunctionalGraph(int n, const vector<int>& adj, const vector<T>& w = vector<int>{}) : N(n), g(N + 1), to(N + 1, -1), represent(N + 1, -1), weight(N + 1) { assert((int)adj.size() == N); assert((int)w.size() == N or w.empty()); for (auto& x : adj) assert(0 <= x and x < N); UnionFind uf(N); for (int i = 0; i < N; i++) { int j = adj[i]; to[i] = j, weight[i] = w.empty() ? T{1} : w[i]; if (uf.same(i, j)) { g[N].emplace_back(N, i, weight[i]); } else { uf.unite(i, j); g[j].emplace_back(j, i, weight[i]); } } calc_represent(N, -1); } // _g は無向グラフ template <typename G> FunctionalGraph(int n, const G& _g) : N(n), g(N + 1), to(N + 1, -1), represent(N + 1, -1), weight(N + 1) { constexpr bool cost_flag = has_cost_v<typename G::value_type::value_type>; WeightedGraph<T> h(n); UnionFind uf(N); for (int i = 0; i < N; i++) { for (auto& j : _g[i]) { if (i > j) continue; T cost; if constexpr (cost_flag) { cost = j.cost; } else { cost = 1; } if (uf.same(i, j)) { // i -> j 向きということにして, i を根とする g[N].emplace_back(N, i, 0); to[i] = j, weight[i] = cost; } else { uf.unite(i, j); h[i].emplace_back(i, j, cost); h[j].emplace_back(j, i, cost); } } } auto dfs = [&](auto rc, int c, int p) -> void { for (auto& d : h[c]) { if (d == p) continue; T cost; if constexpr (cost_flag) { cost = d.cost; } else { cost = 1; } to[d] = c, weight[d] = cost; g[c].emplace_back(c, d, cost); rc(rc, d, c); } }; for (auto& r : g[N]) dfs(dfs, r, -1); calc_represent(N, -1); } vector<vector<int>> get_loops() const { vector<vector<int>> res; for (auto r : g[N]) { vector<int> cur{r}; for (int i = to[r]; i != r; i = to[i]) { cur.push_back(i); } res.push_back(cur); } return res; } // (u, {weight of u-v}) (v, {weight of v-w}), (w, ...) ... vector<vector<pair<int, T>>> get_loops_with_weight() const { vector<vector<pair<int, T>>> res; for (auto r : g[N]) { vector<pair<int, T>> cur{make_pair(r, weight[r])}; for (int i = to[r]; i != r; i = to[i]) { cur.emplace_back(i, weight[i]); } res.push_back(cur); } return res; } private: void calc_represent(int c, int r) { represent[c] = r; for (auto& d : g[c]) calc_represent(d, r == -1 ? d : r); } }; } // namespace FunctionalGraphImpl using FunctionalGraphImpl::FunctionalGraph;