scc

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