This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#include "graph/functional_graph.hpp"
#pragma once #include <algorithm> #include <vector> struct functional_graph { public: functional_graph(int n) : _n(n), graph(n) { } void add_edge(int u, int v) { graph[u].push_back(v); graph[v].push_back(u); } void add_directed_edge(int from, int to) { graph[from].push_back(to); } std::vector<int> loop() { std::vector<int> path; std::vector<int> check(_n, 0); auto dfs = [&](auto dfs, int u, int p) -> int { check[u]++; path.push_back(u); for (int v : graph[u]) { // if (v == p) continue; if (check[v] == 0) { int ret = dfs(dfs, v, u); if (ret != -1) return ret; } else if (check[v] == 1) { return v; } } path.pop_back(); check[u]++; return -1; }; int p = dfs(dfs, 0, -1); std::vector<int>::iterator it = std::find(path.begin(), path.end(), p); return std::vector(it, path.end()); } std::vector<std::vector<std::pair<int, int>>> tree() { std::vector<int> _loop = loop(); std::vector<std::vector<std::pair<int, int>>> ret(_loop.size()); int k = _loop.size(); for (int i = 0; i < k; i++) { auto dfs = [&](auto dfs, int u, int p) -> void { for (int v : graph[u]) { if (v == p) continue; if (v == _loop[i + 1 == k ? 0 : i + 1]) continue; if (v == _loop[i == 0 ? k - 1 : i - 1]) continue; ret[i].emplace_back(u, v); dfs(dfs, v, u); } }; dfs(dfs, _loop[i], -1); } return ret; } private: int _n; std::vector<std::vector<int>> graph; };
#line 2 "graph/functional_graph.hpp" #include <algorithm> #include <vector> struct functional_graph { public: functional_graph(int n) : _n(n), graph(n) { } void add_edge(int u, int v) { graph[u].push_back(v); graph[v].push_back(u); } void add_directed_edge(int from, int to) { graph[from].push_back(to); } std::vector<int> loop() { std::vector<int> path; std::vector<int> check(_n, 0); auto dfs = [&](auto dfs, int u, int p) -> int { check[u]++; path.push_back(u); for (int v : graph[u]) { // if (v == p) continue; if (check[v] == 0) { int ret = dfs(dfs, v, u); if (ret != -1) return ret; } else if (check[v] == 1) { return v; } } path.pop_back(); check[u]++; return -1; }; int p = dfs(dfs, 0, -1); std::vector<int>::iterator it = std::find(path.begin(), path.end(), p); return std::vector(it, path.end()); } std::vector<std::vector<std::pair<int, int>>> tree() { std::vector<int> _loop = loop(); std::vector<std::vector<std::pair<int, int>>> ret(_loop.size()); int k = _loop.size(); for (int i = 0; i < k; i++) { auto dfs = [&](auto dfs, int u, int p) -> void { for (int v : graph[u]) { if (v == p) continue; if (v == _loop[i + 1 == k ? 0 : i + 1]) continue; if (v == _loop[i == 0 ? k - 1 : i - 1]) continue; ret[i].emplace_back(u, v); dfs(dfs, v, u); } }; dfs(dfs, _loop[i], -1); } return ret; } private: int _n; std::vector<std::vector<int>> graph; };