library/Kruskal.java

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

Depends on

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

Verified with

• library/Kruskal_test.java

Code

package library;

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

class Kruskal {
	private static UnionFind uf;
	// O(ElogV)
	public static final long cal(AbstractGraph<? extends WeightedNode, WeightedEdge> g) { return cal(g, null); }
	public static final long cal(AbstractGraph<? extends WeightedNode, WeightedEdge> g, WeightedNode used) { return cal(g.numNode, g.edges(), used); }
	public static final long cal(int numNode, WeightedNode edges) { return cal(numNode, edges, null); }
	public static final long cal(int numNode, WeightedNode edges, WeightedNode used) {
		uf = new UnionFind(numNode);
		if(used != null) used.clear();
		Queue<WeightedEdge> pq = new PriorityQueue<WeightedEdge>();
		for(WeightedEdge e : edges) if(!FastIO.isINF(e.cost)) pq.add(e);

		long cost = 0;
		while(!pq.isEmpty()) {
			WeightedEdge e = pq.poll();
			if(!uf.same(e.source, e.target)) {
				cost += e.cost;
				uf.unite(e);
				if(used != null) used.add(e);
			}
		}
		return cost;
	}
}

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