#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)
// 全ての頂点の出次数が 1
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(x, y) : x に y をマージ
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)
// 全ての頂点の出次数が 1
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;
graph/functional-graph.hpp