package Graph;

import java.util.*;

public class DirectedDFS {

private boolean[] visited;

private int[] pathTo;

private int start;

public DirectedDFS(DirectedGraph g, int s) {

start = s;

visited = new boolean[g.V()];

pathTo = new int[g.V()];

dfs(g, s);

pathTo[s] = s;

}

public void dfs(DirectedGraph g, int v) {

visited[v] = true;

for (int w : g.adj(v)) {

if (!visited[w]) {

pathTo[w] = v;

dfs(g, w);

}

}

}

public boolean hasPathTo(int v) {

return visited[v];

}

public Iterable<Integer> pathTo(int v) {

if (!hasPathTo(v)) return null;

List<Integer> list = new ArrayList<Integer>();

Stack<Integer> stack = new Stack<Integer>();

for (int x = v; x != start; x = pathTo[x]) {

stack.push(x);

}

stack.push(start);

while (!stack.isEmpty()) {

list.add(stack.pop());

}

return list;

}

}