This documentation is automatically generated by online-judge-tools/verification-helper
package library.graph;
import static java.lang.Math.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.function.IntUnaryOperator;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import library.core.VvyLw;
import library.core.interfaces.lambda.RecursiveIntPredicate;
import library.ds.pair.IntPair;
import library.ds.unionfind.UnionFind;
import library.other.SkewHeap;
/**
* グラフクラス
*/
public class Graph extends ArrayList<ArrayList<Edge>> {
private final boolean undirected, weighted;
private final int n, indexed;
private int id;
private final ArrayList<Edge> edge;
private final int[] to;
private final ArrayList<Edge> path;
/**
* コンストラクタ
* @param n 頂点の個数
* @param indexed ?-indexed
* 0-indexedなら0, 1-indexedなら1
* @param undirected 無向グラフかどうか
* 無向グラフならtrue, 有向グラフならfalse
* @param weighted 重みつきかどうか
* 重みつきならtrue, 重みなしならfalse
*/
public Graph(final int n, final int indexed, final boolean undirected, final boolean weighted) {
this.n = n;
this.indexed = indexed;
this.undirected = undirected;
this.weighted = weighted;
id = 0;
edge = new ArrayList<>();
IntStream.range(0, n).forEach(i -> add(new ArrayList<>()));
to = new int[n];
Arrays.fill(to, -1);
path = new ArrayList<>();
}
/**
* グラフ化する
* @param g
* @param undirected
* @param weighted
* @return List<ArrayList<Edge>>をWeightedGraph化したもの
* @apiNote streamでGraphに操作を加えた後に再度グラフに直すときに使えるかも
*/
public static Graph of(final List<ArrayList<Edge>> g, final boolean undirected, final boolean weighted) {
int max = 0, min = Integer.MAX_VALUE;
for(int i = 0; i < g.size(); ++i) {
for(final Edge e: g.get(i)) {
max = max(e.src, e.to);
min = min(e.src, e.to);
}
}
final Graph gp = new Graph(max, min, undirected, weighted);
for(int i = 0; i < g.size(); ++i) {
for(final Edge e: g.get(i)) {
if(weighted) {
gp.addEdge(e.src, e.to, e.cost);
} else {
gp.addEdge(e.src, e.to);
}
}
}
return gp;
}
/**
* 辺を追加する
* @param a
* @param b
*/
public final void addEdge(int a, int b){ addEdge(a, b, 1); }
/**
* 重みつきの辺を追加する
* @param a
* @param b
* @param cost
*/
public final void addEdge(int a, int b, final long cost) {
a -= indexed;
b -= indexed;
this.get(a).add(new Edge(a, b, cost, id));
edge.add(new Edge(a, b, cost, id));
if(undirected) {
this.get(b).add(new Edge(b, a, cost, id));
edge.add(new Edge(b, a, cost, id));
}
id++;
}
/**
* 辺をm個入力する
* @param m 辺の個数
*/
public final void input(final int m) {
IntStream.range(0, m).forEach(i -> {
if(weighted) {
addEdge(VvyLw.io.ni(), VvyLw.io.ni(), VvyLw.io.nl());
} else {
addEdge(VvyLw.io.ni(), VvyLw.io.ni());
}
});
}
/**
* 辺の配列を返す
* @return 辺の配列
*/
public final Edge[] getEdge(){ return edge.toArray(Edge[]::new); }
/**
* グラフを二次元配列にして返す
* @return 二次元配列にしたグラフ
*/
@Override
public final int[][] toArray() {
final int[][] res = new int[n][];
IntStream.range(0, n).forEach(i -> res[i] = get(i).stream().mapToInt(e -> e.to).toArray());
return res;
}
/**
* BFSをして頂点vから各頂点に対する距離を求める
* @param v
*/
public final int[] allDist(final int v) {
final int[] d = new int[n];
Arrays.fill(d, -1);
final Queue<Integer> q = new ArrayDeque<>();
d[v] = 0;
q.add(v);
while(!q.isEmpty()) {
final int tmp = q.poll();
for(final Edge el: this.get(tmp)) {
if(d[el.to] != -1) {
continue;
}
d[el.to] = d[tmp] + 1;
q.add(el.to);
}
}
return d;
}
/**
* 頂点uと頂点vとの距離
* @param u
* @param v
* @return 頂点uと頂点vとの距離
*/
public final int dist(final int u, final int v){ return allDist(u)[v]; }
/**
* トポロジカルソート
*/
public final ArrayList<Integer> topologicalSort() {
final int[] deg = new int[n];
for(int i = 0; i < n; ++i) {
for(final Edge ed: this.get(i)) {
deg[ed.to]++;
}
}
final Stack<Integer> sk = new Stack<>();
for(int i = 0; i < n; ++i) {
if(deg[i] == 0) {
sk.add(i);
}
}
final ArrayList<Integer> ord = new ArrayList<>();
while(!sk.isEmpty()) {
final int tmp = sk.pop();
ord.add(tmp);
for(final Edge ed: this.get(tmp)) {
if(--deg[ed.to] == 0) {
sk.add(ed.to);
}
}
}
return ord.size() == n ? ord : null;
}
/**
* サイクル検出
* @return サイクル
* if non-existence: 空配列
* @apiNote 有向グラフ
*/
public final int[] cycleDetector() {
final int[] used = new int[n];
final Edge[] pre = new Edge[n];
final ArrayList<Edge> cycle = new ArrayList<>();
final RecursiveIntPredicate dfs = (rec, i) -> {
used[i] = 1;
for(final Edge e: get(i)) {
if(used[e.to] == 0) {
pre[e.to] = e;
if(rec.test(rec, e.to)) {
return true;
}
} else if(used[e.to] == 1) {
int now = i;
while(now != e.to) {
cycle.add(pre[now]);
now = pre[now].src;
}
cycle.add(e);
return true;
}
}
used[i] = 2;
return false;
};
for(int i = 0; i < n; ++i) {
if(used[i] == 0 && dfs.test(dfs, i)) {
Collections.reverse(cycle);
return cycle.stream().mapToInt(e -> e.to).toArray();
}
}
return null;
}
private final IntPair dfs(final int i, final int par) {
IntPair ret = IntPair.of(0, i);
for(final Edge e: this.get(i)) {
if(e.to == par) {
continue;
}
final IntPair cost = dfs(e.to, i);
cost.first += e.cost;
if(ret.compareTo(cost) < 0) {
ret = cost;
to[i] = e.to;
}
}
return ret;
}
/**
* path(直径を構成する辺)を構築する
* @return 木の直径
*/
public final long diameter() {
final IntPair p = dfs(0, -1);
final IntPair q = dfs(p.second.intValue(), -1);
int now = p.second.intValue();
while(now != q.second) {
for(final Edge e: this.get(now)) {
if(to[now] == e.to) {
path.add(e);
}
}
now = to[now];
}
return q.first;
}
/**
* pathを返す
* @return 直径を構成する辺
*/
public final Edge[] getPath(){ return path.toArray(Edge[]::new); }
/**
* Dijkstra法
* 負辺のないグラフで単一始点全点間最短路を求める
* @param v
*/
public final ShortestPath dijkstra(final int v) {
final long[] cost = new long[n];
final int[] src = new int[n];
Arrays.fill(cost, Long.MAX_VALUE);
Arrays.fill(src, -1);
final Queue<IntPair> dj = new PriorityQueue<>();
cost[v] = 0;
dj.add(IntPair.of(cost[v], v));
while(!dj.isEmpty()) {
final IntPair tmp = dj.poll();
if(cost[tmp.second.intValue()] < tmp.first.longValue()) {
continue;
}
for(final Edge ed: this.get(tmp.second.intValue())) {
final long next = tmp.first.longValue() + ed.cost;
if(cost[ed.to] <= next) {
continue;
}
cost[ed.to] = next;
src[ed.to] = tmp.second.intValue();
dj.add(IntPair.of(cost[ed.to], ed.to));
}
}
return new ShortestPath(cost, src);
}
/**
* Shortest Path Faster Algorithm
* 負辺が存在していても単一始点全点間最短路を求められる
* 負閉路も検出する
* @param v
*/
public final long[] spfa(final int v) {
final long[] cost = new long[n];
Arrays.fill(cost, Long.MAX_VALUE);
final boolean[] pend = new boolean[n];
final int[] cnt = new int[n];
final Queue<Integer> q = new ArrayDeque<>();
q.add(v);
pend[v] = true;
cnt[v]++;
cost[v] = 0;
while(!q.isEmpty()) {
final int p = q.poll();
pend[p] = false;
for(final Edge e: this.get(p)) {
final long next = cost[p] + e.cost;
if(next >= cost[e.to]) {
continue;
}
cost[e.to] = next;
if(!pend[e.to]) {
if(++cnt[e.to] >= n) {
return null;
}
pend[e.to] = true;
q.add(e.to);
}
}
}
return cost;
}
/**
* Floyd-Warshall法
* 全点対間最短路を求める
*/
public final long[][] floydWarshall() {
final long[][] cost = new long[n][n];
IntStream.range(0, n).forEach(i -> Arrays.fill(cost[i], VvyLw.LINF));
IntStream.range(0, n).forEach(i -> cost[i][i] = 0);
for(int i = 0; i < n; ++i) {
for(final Edge j: this.get(i)) {
cost[i][j.to] = j.cost;
}
}
for(int k = 0; k < n; ++k) {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(cost[i][k] == VvyLw.LINF || cost[k][j] == VvyLw.LINF) {
continue;
}
if(cost[i][j] > cost[i][k] + cost[k][j]) {
cost[i][j] = cost[i][k] + cost[k][j];
}
}
}
}
return cost;
}
/**
* Kruskal法によって最小全域木を求める
*/
public final MST kruskal() {
final UnionFind uf = new UnionFind(n);
final ArrayList<Edge> e = new ArrayList<>();
long res = 0;
for(final Edge ed: edge.stream().sorted(Comparator.comparing(ed -> ed.cost)).collect(Collectors.toList())) {
if(uf.unite(ed.src, ed.to)) {
e.add(ed);
res += ed.cost;
}
}
return new MST(e, res);
}
/**
* 最小有向全域木を求める
* @param v
* @see <a href="https://ei1333.github.io/library/graph/mst/directed-mst.hpp">参考元</a>
*/
public final MST directed(final int v) {
@SuppressWarnings("unchecked")
final ArrayList<Edge> ed = (ArrayList<Edge>) edge.clone();
for(int i = 0; i < n; ++i) {
if(i != v) {
ed.add(new Edge(i, v, 1, 0));
}
}
int x = 0;
final int[] par = new int[2 * n], vis = new int[2 * n], link = new int[2 * n];
Arrays.fill(par, -1);
Arrays.fill(vis, -1);
Arrays.fill(link, -1);
final SkewHeap heap = new SkewHeap(true);
final SkewHeap.Node[] ins = new SkewHeap.Node[2 * n];
Arrays.fill(ins, null);
for(int i = 0; i < ed.size(); i++) {
final Edge e = ed.get(i);
ins[e.to] = heap.push(ins[e.to], e.cost, i);
}
final ArrayList<Integer> st = new ArrayList<>();
final IntUnaryOperator go = z -> {
z = ed.get(ins[z].idx).src;
while(link[z] != -1) {
st.add(z);
z = link[z];
}
for(final int p: st) {
link[p] = z;
}
st.clear();
return z;
};
for(int i = n; ins[x] != null; ++i) {
while(vis[x] == -1) {
vis[x] = 0;
x = go.applyAsInt(x);
}
while(x != i) {
final long w = ins[x].key;
SkewHeap.Node z = heap.pop(ins[x]);
z = heap.add(z, -w);
ins[i] = heap.meld(ins[i], z);
par[x] = i;
link[x] = i;
x = go.applyAsInt(x);
}
while(ins[x] != null && go.applyAsInt(x) == x) {
ins[x] = heap.pop(ins[x]);
}
}
for(int i = v; i != -1; i = par[i]) {
vis[i] = 1;
}
long cost = 0;
final ArrayList<Edge> e = new ArrayList<>();
for(int i = x; i >= 0; i--) {
if(vis[i] == 1) {
continue;
}
cost += ed.get(ins[i].idx).cost;
e.add(ed.get(ins[i].idx));
for(int j = ed.get(ins[i].idx).to; j != -1 && vis[j] == 0; j = par[j]) {
vis[j] = 1;
}
}
return new MST(e, cost);
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; ++i) {
final int m = get(i).size();
sb.append(i + ": [");
for(int j = 0; j < m; ++j) {
if(weighted) {
sb.append("(to: " + get(i).get(j).to + ", cost: " + get(i).get(j).cost + ')');
} else {
sb.append(get(i).get(j).to);
}
if(j + 1 < m) {
sb.append(", ");
}
}
sb.append(']');
if(i + 1 < n) {
sb.append('\n');
}
}
return sb.toString();
}
}
Traceback (most recent call last):
File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/user_defined.py", line 68, in bundle
raise RuntimeError('bundler is not specified: {}'.format(str(path)))
RuntimeError: bundler is not specified: Java/library/graph/Graph.java