``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 ``` ```package algs42; import stdlib.*; import algs13.Stack; /* *********************************************************************** * Compilation: javac DepthFirstDirectedPaths.java * Execution: java DepthFirstDirectedPaths G s * Dependencies: Digraph.java Stack.java * * Determine reachability in a digraph from a given vertex using * depth first search. * Runs in O(E + V) time. * * % tinyDG.txt 3 * 3 to 0: 3-5-4-2-0 * 3 to 1: 3-5-4-2-0-1 * 3 to 2: 3-5-4-2 * 3 to 3: 3 * 3 to 4: 3-5-4 * 3 to 5: 3-5 * 3 to 6: not connected * 3 to 7: not connected * 3 to 8: not connected * 3 to 9: not connected * 3 to 10: not connected * 3 to 11: not connected * 3 to 12: not connected * *************************************************************************/ public class DepthFirstDirectedPaths { private final boolean[] marked; // marked[v] = true if v is reachable from s private final int[] edgeTo; // edgeTo[v] = last edge on path from s to v private final int s; // source vertex // single source public DepthFirstDirectedPaths(Digraph G, int s) { marked = new boolean[G.V()]; edgeTo = new int[G.V()]; this.s = s; dfs(G, s); } private void dfs(Digraph G, int v) { marked[v] = true; for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; dfs(G, w); } } } // is there a directed path from s to v? public boolean hasPathTo(int v) { return marked[v]; } // return path from s to v; null if no such path public Iterable pathTo(int v) { if (!hasPathTo(v)) return null; Stack path = new Stack<>(); for (int x = v; x != s; x = edgeTo[x]) path.push(x); path.push(s); return path; } public static void main(String[] args) { args = new String[] { "data/tinyDG.txt", "3" }; In in = new In(args[0]); Digraph G = DigraphGenerator.fromIn(in); // StdOut.println(G); int s = Integer.parseInt(args[1]); DepthFirstDirectedPaths dfs = new DepthFirstDirectedPaths(G, s); for (int v = 0; v < G.V(); v++) { if (dfs.hasPathTo(v)) { StdOut.format("%d to %d: ", s, v); for (int x : dfs.pathTo(v)) { if (x == s) StdOut.print(x); else StdOut.print("-" + x); } StdOut.println(); } else { StdOut.format("%d to %d: not connected\n", s, v); } } } } ```