This documentation is automatically generated by online-judge-tools/verification-helper
#include "graph/quotient_graph.hpp"component_id(n, groups): 頂点 v の成分番号を id[v] とする長さ n の列を返す。groups が atcoder::scc_graph::scc() の結果なら辺 $(u, v)$ について id[u] <= id[v]。quotient_graph(g, groups): 隣接リスト g の辺を成分間に写したグラフの隣接リストを返す。q[i] は成分 i から出る辺の先の成分番号で、重複がなく昇順。groups は $0, \ldots, n - 1$ の分割。atcoder::scc_graph::scc()、lowlink::two_edge_connected_components()、atcoder::dsu::groups() の結果はこれを満たす。component_id: $\mathcal{O}(N)$quotient_graph: $\mathcal{O}(N + M \log M)$#pragma once
#include <algorithm>
#include <vector>
inline std::vector<int> component_id(int n, const std::vector<std::vector<int>>& groups) {
std::vector<int> id(n);
for (int i = 0; i < int(groups.size()); i++) {
for (int v : groups[i]) id[v] = i;
}
return id;
}
inline std::vector<std::vector<int>> quotient_graph(const std::vector<std::vector<int>>& g, const std::vector<std::vector<int>>& groups) {
std::vector<int> id = component_id(int(g.size()), groups);
std::vector<std::vector<int>> q(groups.size());
for (int u = 0; u < int(g.size()); u++) {
for (int v : g[u]) {
if (id[u] != id[v]) q[id[u]].push_back(id[v]);
}
}
for (auto& es : q) {
std::ranges::sort(es);
es.erase(std::ranges::unique(es).begin(), es.end());
}
return q;
}#line 2 "graph/quotient_graph.hpp"
#include <algorithm>
#include <vector>
inline std::vector<int> component_id(int n, const std::vector<std::vector<int>>& groups) {
std::vector<int> id(n);
for (int i = 0; i < int(groups.size()); i++) {
for (int v : groups[i]) id[v] = i;
}
return id;
}
inline std::vector<std::vector<int>> quotient_graph(const std::vector<std::vector<int>>& g, const std::vector<std::vector<int>>& groups) {
std::vector<int> id = component_id(int(g.size()), groups);
std::vector<std::vector<int>> q(groups.size());
for (int u = 0; u < int(g.size()); u++) {
for (int v : g[u]) {
if (id[u] != id[v]) q[id[u]].push_back(id[v]);
}
}
for (auto& es : q) {
std::ranges::sort(es);
es.erase(std::ranges::unique(es).begin(), es.end());
}
return q;
}