Skip to content

tarjanScc ​

tarjanScc(graph) divide un grafo dirigido en componentes fuertemente conexos mediante el recorrido de bajo enlace de Tarjan. Acepta una lista de adyacencia o Graph<N, W>.

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

Cada array interno contiene vértices que se alcanzan mutuamente. El orden depende del recorrido.

Ejemplo ​

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

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

Resultado de estudio ​

tyrus
interface TarjanSccInfo {
    components: usize[][];
    componentCount: usize;
    examinedEdgeCount: usize;
    stackOperationCount: usize;
    discoveryIndices: usize[];
    lowLinks: usize[];
    stackPushCount: usize;
    stackPopCount: usize;
}
tyrus
import { SccInfo, TarjanSccInfo, tarjanSccInfo } from "tyrus:algorithm";
const info: TarjanSccInfo = tarjanSccInfo([[1], [2], [0, 3], [4], [3]]);
print(info.components); // [[4, 3], [2, 1, 0]]
print(info.componentCount); // 2
print(info.examinedEdgeCount); // 6
print(info.stackOperationCount); // 10
print(info.discoveryIndices); // [0, 1, 2, 3, 4]
print(info.lowLinks); // [0, 1, 2, 3, 4]
print(info.stackPushCount); // 5
print(info.stackPopCount); // 5