Skip to content

kosarajuScc ​

kosarajuScc(graph) partitions a directed graph into strongly connected components using a finishing-order traversal followed by traversal of the reversed graph. It accepts an adjacency list or Graph<N, W>.

SignatureReturnsComplexity
kosarajuScc(graph: usize[][])usize[][]O(V + E)
kosarajuScc(graph: Graph<N, W>)usize[][]O(V + E)

Each returned inner array is one maximal mutually reachable set of vertices. Component ordering is not a stability guarantee.

Example ​

tyrus
import { kosarajuScc } from "tyrus:algorithm";

const components: usize[][] = kosarajuScc([[1], [0]]);
print(components.length);  // 1

Study result ​

tyrus
interface KosarajuSccInfo {
    components: usize[][];
    componentCount: usize;
    examinedEdgeCount: usize;
    stackOperationCount: usize;
    finishingOrder: usize[];
    firstTraversalEdgeCount: usize;
    secondTraversalEdgeCount: usize;
}
tyrus
import { KosarajuSccInfo, SccInfo, kosarajuSccInfo } from "tyrus:algorithm";
const info: KosarajuSccInfo = kosarajuSccInfo([[1], [2], [0, 3], [4], [3]]);
print(info.components); // [[0, 2, 1], [3, 4]]
print(info.componentCount); // 2
print(info.examinedEdgeCount); // 6
print(info.stackOperationCount); // 0
print(info.finishingOrder); // [0, 1, 2, 3, 4]
print(info.firstTraversalEdgeCount); // 6
print(info.secondTraversalEdgeCount); // 6