package cpecmu.cpe218.sp2019.hw1.submit;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.List;
import java.util.Scanner;

import cpecmu.cpe218.sp2019.Graph;
import cpecmu.cpe218.sp2019.GraphAdjList;
import cpecmu.cpe218.sp2019.Pair;
import cpecmu.cpe218.sp2019.hw1.DAGger;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

public class DAGgerImpl implements DAGger {

    /** input file name */
    protected static final String inFile = "hw1tests/dagger03.in";

    @Override
    public <V> Pair<Boolean, List<V>> hasTopoOrCycle(Graph<V> g) {
          Map<V,Boolean> visited = new HashMap();
          Stack<V> stack = new Stack<V>();

          for(V v:g.vertices()) {
              visited.put(v, false);
          }

         //findSCC
         for(V v : g.vertices()){
             if(visited.get(v)==false){
                 fillOrder(g,visited,v,stack);
             }
         }
         Graph <V> revG = revGraph(g);
        //mark all v not visited for sec DFS
         for(V v:g.vertices()) {
              visited.put(v, false);
          }

         while(stack.empty()==false){
            V pop = stack.pop();
            if(visited.get(pop)==false){
                DFS(revG,visited,pop);

                System.out.println();

            }
         }


          return new Pair<>(true,null);


    }

    public <V> Graph<V> revGraph(Graph<V> g){
         Graph<V> revG = new GraphAdjList();
         for(V v : g.vertices()){
             revG.addVertex(v);

         }
         for(V v: g.vertices()){
         for(V w: g.adjacentFrom(v)){
                 revG.addEdge(w, v);
           }
         }
         /*
         for(V v: revG.vertices()){
            System.out.println(v + " ->" + revG.adjacentFrom(v));
         }
          */
         return revG;
    }
    public <V> void fillOrder(Graph<V> g,Map<V,Boolean> visited,V v,Stack stack){
        visited.put(v, true);
        for(V w: g.adjacentFrom(v)){
            //System.out.print(visited.get(w)+" ");
            if(visited.get(w)==false){

                fillOrder(g,visited,w,stack);

            }
        }
        stack.push(v);
    }
    public <V> void DFS(Graph<V> g, Map<V,Boolean> visited ,V v){

           visited.put(v, true);
           System.out.print(v + " ");


            for(V w : g.adjacentFrom(v)){
                if(visited.get(w)==false){

                    DFS(g,visited,w);


                }
            }




    }

    public static void main(String[] args) {
        try (FileReader fr = new FileReader(inFile);
             Scanner s = new Scanner(fr)) {
            Graph<String> g = new GraphAdjList<>();
            // read graph
            int n = s.nextInt();
            for (int i = 0; i < n; i++)
                g.addVertex(s.next());
            int m = s.nextInt();
            for (int i = 0; i < m; i++)
                g.addEdge(s.next(), s.next());

            // invoke algorithm
            DAGger sbm = new DAGgerImpl();
            Pair<Boolean, List<String>> res = sbm.hasTopoOrCycle(g);
            System.out.println("Has " + (res.fst() ? "DAG" : "cycle"));
            System.out.println(res.snd());
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }

}