import java.util.*;

class Graph{
    LinkedList<Integer>[] adjList;
    int visited[];
    public Graph(int nodes){
        adjList = new LinkedList[nodes];
        visited = new int[this.adjList.length];
        for(int i = 0; i < nodes; i++){
            adjList[i] = new LinkedList<>();
        }
    }

    public void addNode(int src, int dest){
        adjList[src].addFirst(dest);
        // adjList[dest].addFirst(src);  //-- uncomment this for undirected graph.
    }

    public static void printG(Graph g1){

        for(int i = 0; i < g1.adjList.length; i++){
            System.out.print("Node :"+i);
            for(Integer j : g1.adjList[i]){
                System.out.print(" -> "+j);
            }
            System.out.println();
        }
    }

    // this function will not work in disconnected Graphs
    public void bfs(int start){

        Queue<Integer> q = new LinkedList<>();

        visited[start] = 1;
        q.add(start);

        while(!q.isEmpty()){
            int item = q.poll();
            System.out.println(item + " ");

            Iterator<Integer> i = this.adjList[item].listIterator();
            while(i.hasNext()){
                int temp = i.next();
                if (visited[temp] != 1) {
                    visited[temp] = 1;
                    q.add(temp);
                }
            }
        }
    }

    // function for BFS in disconnected graph:
    public void bfsDisc(int start){
        bfs(start);
        for (int i = 0; i < this.visited.length; i++) {
            if (this.visited[i] == 0) {
                this.bfs(i);
            }
        }
    }

    // function for DFS in Graph
    public void dfs(int start) {
        Stack <Integer>st = new Stack<Integer>();
        visited[start] = 1;
        st.push(start);

        while(!st.isEmpty()){
            int item = st.pop();
            System.out.println(item);

            Iterator it = this.adjList[item].iterator();
            while(it.hasNext()){
                int i = (Integer)it.next();
                if(this.visited[i] != 1){
                    this.visited[i] = 1;
                    st.push(i);
                }
            }
        }
    }

    public void dfsDisc(int start) {
        dfs(start);
        for (int i = 0; i < this.visited.length; i++) {
            if (this.visited[i] == 0) {
                this.dfs(i);
            }
        }
    }

// ----------------------- Main --------------
    public static void main(String[] args) {

        // Graph must have '0' node.

        Graph g = new Graph(6);
        g.addNode(0, 2);
        g.addNode(0, 5);
        g.addNode(1, 2);
        g.addNode(1, 4);
        g.addNode(2, 0);
        g.addNode(2, 1);
        g.addNode(2, 4);
        g.addNode(2, 5);
        g.addNode(3, 2);
        g.addNode(3, 4);
        g.addNode(4, 1);
        g.addNode(4, 2);
        g.addNode(4, 3);
        g.addNode(4, 5);
        g.addNode(5, 4);
        g.addNode(5, 0);

        printG(g);
        System.out.println("DFS");
        g.dfsDisc(0);

        Graph g1 = new Graph(7);
        g1.addNode(0, 1);
        g1.addNode(1, 2);
        g1.addNode(1, 3);
        g1.addNode(2, 4);
        g1.addNode(3, 5);
        g1.addNode(3, 6);

        // printG(g1);
        // System.out.println("BFS");
        // g.bfsDisc(1);

        // System.out.println("DFS");
        // g1.dfsDisc(1);

    }
}