import java.util.Set;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Stack;

public class GraphSearch {
    public static <E> void DFS1(Graph<E> g, E v) {
        GraphSearch.DFS1(g, v, new HashSet<E>());
    }
    
    private static <E> void DFS1(Graph<E> g, E v, Set<E> visited) {
        if (!visited.contains(v)) {
            System.out.println(v);
            visited.add(v);
            for (E adj : g.getAdj(v)) {
                GraphSearch.DFS1(g, adj, visited);
            }
        }
    }
    
    public static <E> void DFS2(Graph<E> g, E v) {
        Stack<E> unvisited = new Stack<E>();
        unvisited.push(v);
        Set<E> visited = new HashSet<E>();
        while (!unvisited.isEmpty()) {
            E nextV = unvisited.pop();
            if (!visited.contains(nextV)) {
                System.out.println(nextV);
                visited.add(nextV);
                for (E adj : g.getAdj(nextV)) {
                    unvisited.push(adj);
                }
            }
        }
    }
    
    public static <E> void BFS(Graph<E> g, E v) {
        Queue<E> unvisited = new LinkedList<E>();
        unvisited.add(v);
        Set<E> visited = new HashSet<E>();
        while (!unvisited.isEmpty()) {
            E nextV = unvisited.remove();
            if (!visited.contains(nextV)) {
                System.out.println(nextV);
                visited.add(nextV);
                for (E adj : g.getAdj(nextV)) {
                    unvisited.add(adj);
                }
            }
        }
    }
    
    public static <E> void topo(Graph<E> g, E v) {
        GraphSearch.topo(g, v, new HashSet<E>());
    }
    private static <E> void topo(Graph<E> g, E v, Set<E> visited) {
        if (!visited.contains(v)) {
            visited.add(v);
            for (E adj : g.getAdj(v)) {
                GraphSearch.topo(g, adj, visited);
            }
            System.out.println(v);
        }
    }

    
    ////////////////////////////////////////////////////////
    
    public static void main(String[] args) {
        Graph<String> teams = new DiGraphList<String>();
        teams.addEdge("Packers", "Bears");
        teams.addEdge("Packers", "Broncos");
        teams.addEdge("Broncos", "Dolphins");
        teams.addEdge("Broncos", "Chiefs");
        teams.addEdge("Chiefs", "Colts");
        teams.addEdge("Bears", "Bucs");
        teams.addEdge("Bucs", "Colts");
        teams.addEdge("Bears", "Falcons");
        teams.addEdge("Falcons", "Titans");
        teams.addEdge("Titans", "Colts");   
        teams.addEdge("Falcons", "Seahawks");
        teams.addEdge("Seahawks", "Cardinals");
        teams.addEdge("Cardinals", "Rams");
        
        GraphSearch.DFS1(teams, "Packers");
        
        System.out.println();
        
        GraphSearch.DFS2(teams, "Packers");
        
        System.out.println();
        
        GraphSearch.BFS(teams, "Packers");        

        System.out.println();
        
        GraphSearch.topo(teams, "Packers");  
    }
}