library/Scc.java

• View this file on GitHub
• Last update: 2023-03-25 01:16:43+09:00

Depends on

• library/AbstractGraph.java
• library/FastIO.java

Required by

• library/TwoSat.java

Verified with

• library/Scc_graph_test.java
• library/Scc_groups_test.java
• library/Scc_ids_test.java

Code

package library;

import java.util.*;
import library.FastIO;
import library.AbstractGraph;

final class Scc {
	private static int ids[];
	private static int numGroup;

	// O(V+E)
	public static final <Edge extends AbstractEdge<Edge>> int[][] calGroups(final AbstractGraph<? extends AbstractNode<Edge>, Edge> g) { return calGroups(g.numNode, g.numEdge(), g.nodes()); }
	public static final <Edge extends AbstractEdge<Edge>> int[][] calGroups(final int numNode, final int numEdge, final AbstractNode<Edge>[] nodes) {
		int ids[] = calIds(numNode, numEdge, nodes);
		int len[] = new int[numGroup];
		for(int x : ids) len[x] ++;
		int groups[][] = new int[numGroup][];
		for(int i = 0; i < numGroup; i ++) groups[i] = new int[len[i]];
		Arrays.fill(len, 0);
		for(int i = 0; i < numNode; i ++) groups[ids[i]][len[ids[i]] ++] = i;
		return groups;
	}
	public static final <Edge extends AbstractEdge<Edge>> UnweightedSetGraph calGraph(final AbstractGraph<? extends AbstractNode<Edge>, Edge> g) { return calGraph(g.numNode, g.numEdge(), g.nodes()); }
	public static final <Edge extends AbstractEdge<Edge>> UnweightedSetGraph calGraph(final int numNode, final int numEdge, final AbstractNode<Edge>[] nodes) {
		int ids[] = calIds(numNode, numEdge, nodes);
		var contracted = new UnweightedSetGraph(numGroup, true);
		for(int i = 0; i < numNode; i ++) {
			for(Edge e : nodes[i]) {
				int s = ids[e.source];
				int t = ids[e.target];
				if(s != t) contracted.add(s, t);
			}
		}
		return contracted;
	}
	public static final <Edge extends AbstractEdge<Edge>> int[] calIds(final AbstractGraph<? extends AbstractNode<Edge>, Edge> g) { return calIds(g.numNode, g.numEdge(), g.nodes()); }
	public static final <Edge extends AbstractEdge<Edge>> int[] calIds(final int numNode, final int numEdge, final AbstractNode<Edge>[] nodes) {
		int low[] = new int[numNode];
		int ids[] = new int[numNode];
		int visited[] = new int[numNode];
		int ptr1 = 0;
		int stack[] = new int[numEdge + 1];
		int ptr2 = 0;
		int now = 0;
		int numGroup = 0;
		Arrays.fill(low, -1);
		for(int i = 0; i < numNode; i ++) {
			if(low[i] != -1) continue;
			stack[ptr2 ++] = i;
			while(ptr2 != 0) {
				int v = stack[-- ptr2];
				if(v >= 0) {
					if(low[v] != -1) continue;
					low[v] = now ++;
					visited[ptr1 ++] = v;
					stack[ptr2 ++] = - v - 1;
					for(Edge e : nodes[v]) if(low[e.target] == -1) stack[ptr2 ++] = e.target;
				}else {
					v = - v - 1;
					boolean root = true;
					for(Edge e : nodes[v]) if(low[v] > low[e.target]) { low[v] = low[e.target]; root = false; }
					if(root) {
						while(true) {
							int u = visited[-- ptr1];
							low[u] = numNode;
							ids[u] = numGroup;
							if(u == v) break;
						}
						numGroup ++;
					}
				}
			}
		}

		for(int i = 0; i < numNode; i ++) ids[i] = numGroup - ids[i] - 1;
		Scc.ids = ids;
		Scc.numGroup = numGroup;
		return ids;
	}
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/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 "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/user_defined.py", line 71, in bundle
    return subprocess.check_output(shlex.split(command))
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/subprocess.py", line 466, in check_output
    return run(*popenargs, stdout=PIPE, timeout=timeout, check=True,
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/subprocess.py", line 571, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['false']' returned non-zero exit status 1.

Back to top page