package Graph;

import java.util.*;

public class DepthFirstSearch {

private boolean[] visited;

private int count;

private int[] edgeTo;

private int start;

public DepthFirstSearch(Graph g, int start) {

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

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

this.start = start;

dfs(g, start);

}

public void dfs(Graph g, int s) {

visited[s] = true;

count++;

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

if (!visited[w]) {

edgeTo[w] = s;

dfs(g, w);

}

}

}

public boolean visited(int v) {

return visited[v];

}

public int count() {

return count;

}

public boolean hasPathTo(int v) {

return visited[v];

}

public Iterable<Integer> pathTo(int v) {

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

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

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

stack.push(x);

}

stack.push(start);

while(!stack.isEmpty()) {

path.add(stack.pop());

}

return path;

}

}