dunkelheit reference

dkh.graph.scc

  • SCCInfo

    Declaration

    struct SCCInfo;

    強連結成分の情報

    • id

      Declaration

      int[] id;

      頂点id -> 強連結成分id

    • groups

      Declaration

      int[][] groups;

      強連結成分id -> その連結成分の頂点idたち

    • group

      Declaration

      const const(int[]) group(size_t i);

      iと同じgroupの頂点を返す

  • scc

    Declaration

    SCCInfo scc(T)(T g);

    強連結成分分解

    Examples

    1. import std.algorithm, std.typecons; alias E = Tuple!(int, "to"); E[][] g = new E[][5]; g[0] ~= E(1); g[1] ~= E(2); g[2] ~= E(0); g[2] ~= E(3); g[3] ~= E(4); g[4] ~= E(3); auto info = scc(g); assert(info.id[0] == info.id[1] && info.id[1] == info.id[2]); assert(info.id[3] == info.id[4]); assert(info.id[0] < info.id[3]); //idはトポロジカル順 assert(equal(info.group(0).dup.sort!"a<b", [0, 1, 2])); assert(equal(info.group(3).dup.sort!"a<b", [3, 4]));