graphtccomp.java

来自「个人学习图算法时写的源码 包括最小生成树, 最大网络流, DSF遍历, BSF」· Java 代码 · 共 27 行

package twf.graph.directed;

import twf.adt.graph.AdjList;
import twf.adt.graph.Graph;
import twf.graph.DenseGraph;
import twf.graph.Edge;

public class GraphTCcomp {
	private DagTC ktc;
	private GraphSC gSC;
	public GraphTCcomp(Graph G) 
	  {
		gSC = new KosarajuGraphSC(G);
		DenseGraph kernel = new DenseGraph(gSC.count(), true);
		for (int v = 0; v < G.V(); v++)
	       {
	        AdjList A = G.getAdjList(v);
	        for (int t = A.beg(); !A.end(); t = A.nxt())
	          kernel.insert(new Edge(gSC.id(v), gSC.id(t)));
	       }
	      ktc = new DagTC(kernel);
	  }
	public boolean reachable(int v, int w)
	  { return ktc.reachable(gSC.id(v), gSC.id(w));}

}