1 module dkh.graph.dfstree; 2 3 struct DFSTreeInfo { 4 int[] low, ord, par, vlis; //low, ord, parent, visitList 5 int[][] tr; //dfs tree(directed) 6 this(int n) { 7 low = new int[n]; 8 ord = new int[n]; 9 par = new int[n]; 10 vlis = new int[n]; 11 tr = new int[][](n); 12 } 13 } 14 15 DFSTreeInfo dfsTree(T)(T g) { 16 import std.algorithm : min, each, filter; 17 import std.conv : to; 18 const int n = g.length.to!int; 19 auto info = DFSTreeInfo(n); 20 with(info) { 21 int co = 0; 22 bool[] used = new bool[](n); 23 void dfs(int p, int b) { 24 used[p] = true; 25 low[p] = ord[p] = co++; 26 par[p] = b; 27 28 bool rt = true; 29 foreach (e; g[p]) { 30 int d = e.to; 31 if (rt && d == b) { 32 rt = false; 33 continue; 34 } 35 if (!used[d]) { 36 dfs(d, p); 37 low[p] = min(low[p], low[d]); 38 } else { 39 low[p] = min(low[p], ord[d]); 40 } 41 } 42 } 43 44 foreach (i; 0..n) { 45 if (used[i]) continue; 46 dfs(i, -1); 47 } 48 foreach (i; 0..n) { 49 if (par[i] == -1) continue; 50 tr[par[i]] ~= i; 51 } 52 // par.filter!"a!=-1".each!((i, v) => tr[v] ~= i.to!int); 53 ord.each!((i, v) => vlis[v] = i.to!int); 54 } 55 return info; 56 }