Code:
import java.util.*;
public class DfsPaths {
private boolean marked[];
private int[] edgeTo;
private final int s;
public DfsPaths(Graph g, int s) {
this.marked = new boolean[g.V()];
this.edgeTo = new int[g.V()];
this.s = s;
dfs(g, s);
}
private void dfs(Graph g, int v) {
marked[v] = true;
for(int w : g.adj(v)) {
if(!marked[w]) {
edgeTo[w] = v;
dfs(g, w);
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if(!hasPathTo(v)) return null;
Stack<Integer> 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) {
Graph g = new Graph(5);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(0, 3);
DfsPaths dp = new DfsPaths(g, 1);
System.out.println(dp.hasPathTo(0));
for(int i : dp.pathTo(0)) {
System.out.println(i);
}
}
}
