Skip to content

kosarajuScc ​

kosarajuScc(graph) divide um grafo direcionado em componentes fortemente conexos usando a ordem de finalização e o grafo reverso. Aceita uma lista de adjacência ou Graph<N, W>.

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

Cada array interno é um conjunto maximal de vértices mutuamente alcançáveis.

Exemplo ​

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

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

Resultado de estudo ​

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