VvyLw's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub

:warning: Java/library/graph/SCC.java

Depends on

Required by

Code

package library.graph;

import static java.lang.Math.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.IntStream;

import library.core.Utility;
import library.core.VvyLw;

/**
 * 強連結成分分解(Strongly Connected Components)
 * @see <a href="https://github.com/NASU41/AtCoderLibraryForJava/tree/master/SCC">参考元</a>
 */
public final class SCC {
	private final int n, indexed;
	private int m;
	private final ArrayList<Edge> edge;
	private final int[] start, ids;
	private int[][] groups;
	private boolean notBuilt;
	/**
	 * コンストラクタ
	 * 1-indexed
	 * @param n
	 */
	public SCC(final int n){ this(n, 1); }
	/**
	 * コンストラクタ
	 * 有向グラフを作る
	 * @param n サイズ
	 * @param indexed
	 */
	public SCC(final int n, final int indexed) {
		this.n = n;
		this.indexed = indexed;
		edge = new ArrayList<>();
		start = new int[n + 1];
		ids = new int[n];
		m = 0;
		notBuilt = true;
	}
	/**
	 * 辺を追加する
	 * @param from
	 * @param to
	 */
	public final void addEdge(int from, int to) {
		from -= indexed;
		to -= indexed;
		rangeCheck(from);
		rangeCheck(to);
		edge.add(new Edge(from, to, 1, m++));
		start[from + 1]++;
	}
	/**
	 * 辺をm個入力する
	 * @param m
	 */
	public final void input(final int m){ IntStream.range(0, m).forEach(i -> addEdge(VvyLw.io.ni(), VvyLw.io.ni())); }
	/**
	 * 頂点iの強連結成分の頂点番号を返す
	 * @param i
	 * @return 頂点iの強連結成分の頂点番号
	 */
	public final int id(final int i) {
		if(notBuilt) {
			throw new UnsupportedOperationException("Graph hasn't been built.");
		}
		rangeCheck(i);
		return ids[i];
	}
	/**
	 * 構築
	 */
	public final void build() {
		for(int i = 1; i <= n; i++) {
			start[i] += start[i - 1];
		}
		final Edge[] ed = new Edge[m];
		final int[] count = new int[n + 1];
		System.arraycopy(start, 0, count, 0, n + 1);
		for(final Edge e: edge) {
			ed[count[e.src]++] = e;
		}
		int nowOrd = 0, groupNum = 0, k = 0, ptr = 0;
		final int[] par = new int[n], vis = new int[n], low = new int[n], ord = new int[n];
		Arrays.fill(ord, -1);
		final long[] stack = new long[n];
		for(int i = 0; i < n; i++) {
			if(ord[i] >= 0) {
				continue;
			}
			par[i] = -1;
			stack[ptr++] = 0L << 32 | i;
			while(ptr > 0) {
				long p = stack[--ptr];
				int u = (int) (p & 0xffff_ffffl);
				int j = (int) (p >>> 32);
				if(j == 0) {
					low[u] = ord[u] = nowOrd++;
					vis[k++] = u;
				}
				if(start[u] + j < count[u]) {
					int to = ed[start[u] + j].to;
					stack[ptr++] += 1l << 32;
					if(ord[to] == -1) {
						stack[ptr++] = 0l << 32 | to;
						par[to] = u;
					} else {
						low[u] = min(low[u], ord[to]);
					}
				} else {
					while(j --> 0) {
						final int to = ed[start[u] + j].to;
						if(par[to] == u) {
							low[u] = min(low[u], low[to]);
						}
					}
					if(low[u] == ord[u]) {
						while(true) {
							final int v = vis[--k];
							ord[v] = n;
							ids[v] = groupNum;
							if(v == u) {
								break;
							}
						}
						groupNum++;
					}
				}
			}
		}
		for(int i = 0; i < n; i++) {
			ids[i] = groupNum - 1 - ids[i];
		}        
		final int[] counts = new int[groupNum];
		for(final int x: ids) {
			counts[x]++;
		}
		groups = new int[groupNum][];
		for(int i = 0; i < groupNum; i++) {
			groups[i] = new int[counts[i]];
		}
		for(int i = 0; i < n; i++) {
			int cmp = ids[i];
			groups[cmp][--counts[cmp]] = i;
		}
		notBuilt = false;
	}
	/**
	 * 各強連結成分についてそれに属する頂点を返す
	 * @return 各強連結成分についてそれに属する頂点
	 */
	public final int[][] groups() {
		if(notBuilt) {
			throw new UnsupportedOperationException("Graph hasn't been built.");
		}
		return groups;
	}
	private final void rangeCheck(final int i) {
		if(!Utility.scope(0, i, n - 1)) {
			throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, n));
		}
	}
}
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/SCC.java
Back to top page