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>.
| Signature | Returns | Complexity |
|---|---|---|
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); // 1Study 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