import java.util.*;

public class UnweightedGraph<V> implements Graph<V> {
  protected List<V> vertices = new ArrayList<>(); // Przechowuje wierzchołki 
  protected List<List<Edge>> neighbors 
    = new ArrayList<>(); // Lista sąsiedztwa krawędzi

  /** Tworzy pusty graf */
  public UnweightedGraph() {
  }
  
  /** Tworzy graf na podstawie wierzchołków i krawędzi zapisanych w tablicach */
  public UnweightedGraph(V[] vertices, int[][] edges) {
    for (int i = 0; i < vertices.length; i++)
      addVertex(vertices[i]);
    
    createAdjacencyLists(edges, vertices.length);
  }

  /** Tworzy graf na podstawie wierzchołków i krawędzi zapisanych na listach */
  public UnweightedGraph(List<V> vertices, List<Edge> edges) {
    for (int i = 0; i < vertices.size(); i++)
      addVertex(vertices.get(i));
        
    createAdjacencyLists(edges, vertices.size());
  }

  /** Tworzy graf z wierzchołkami całkowitoliczbowymi 0, 1, 2 itd. i listą krawędzi */
  public UnweightedGraph(List<Edge> edges, int numberOfVertices) {
    for (int i = 0; i < numberOfVertices; i++) 
      addVertex((V)(Integer.valueOf(i))); // Wierzchołki to {0, 1, . . . }
    
    createAdjacencyLists(edges, numberOfVertices);
  }

  /** Tworzy graf z wierzchołkami całkowitoliczbowymi 0, 1, 2 itd. i tablicą krawędzi */
  public UnweightedGraph(int[][] edges, int numberOfVertices) {
    for (int i = 0; i < numberOfVertices; i++) 
      addVertex((V)(Integer.valueOf(i))); // Wierzchołki to {0, 1, . . . }
    
    createAdjacencyLists(edges, numberOfVertices);
  }

  /** Tworzy listę sąsiedztwa dla każdego wierzchołka */
  private void createAdjacencyLists(
      int[][] edges, int numberOfVertices) {
    for (int i = 0; i < edges.length; i++) {
      addEdge(edges[i][0], edges[i][1]);
    }
  }

  /** Tworzy listę sąsiedztwa dla każdego wierzchołka */
  private void createAdjacencyLists(
      List<Edge> edges, int numberOfVertices) {
    for (Edge edge: edges) {
      addEdge(edge.u, edge.v);
    }
  }

  @Override /** Zwraca liczbę wierzchołków w grafie */
  public int getSize() {
    return vertices.size();
  }

  @Override /** Zwraca wierzchołki grafu */
  public List<V> getVertices() {
    return vertices;
  }

  @Override /** Zwraca wierzchołek o podanym indeksie */
  public V getVertex(int index) {
    return vertices.get(index);
  }

  @Override /** Zwraca indeks podanego wierzchołka */
  public int getIndex(V v) {
    return vertices.indexOf(v);
  }

  @Override /** Zwraca sąsiadów podanego wierzchołka */
  public List<Integer> getNeighbors(int index) {
    List<Integer> result = new ArrayList<>();
    for (Edge e: neighbors.get(index))
      result.add(e.v);
    
    return result;
  }

  @Override /** Zwraca stopień podanego wierzchołka */
  public int getDegree(int v) {
    return neighbors.get(v).size();
  }

  @Override /** Wyświetla krawędzie */
  public void printEdges() {
    for (int u = 0; u < neighbors.size(); u++) {
      System.out.print(getVertex(u) + " (" + u + "): ");
      for (Edge e: neighbors.get(u)) {
        System.out.print("(" + getVertex(e.u) + ", " +
          getVertex(e.v) + ") ");
      }
      System.out.println();
    }
  }

  @Override /** Opróżnianie grafu */
  public void clear() {
    vertices.clear();
    neighbors.clear();
  }
  
  @Override /** Dodaje wierzchołek do grafu */
  public boolean addVertex(V vertex) {
    if (!vertices.contains(vertex)) {
      vertices.add(vertex);
      neighbors.add(new ArrayList<Edge>());
      return true;
    }
    else {
      return false;
    }
  }

  @Override /** Dodaje krawędź do grafu */
  public boolean addEdge(Edge e) {
    if (e.u < 0 || e.u > getSize() - 1)
      throw new IllegalArgumentException("Brak indeksu: " + e.u);

    if (e.v < 0 || e.v > getSize() - 1)
      throw new IllegalArgumentException("Brak indeksu: " + e.v);
    
    if (!neighbors.get(e.u).contains(e)) {
      neighbors.get(e.u).add(e);
      return true;
    }
    else {
      return false;
    }
  }
  
  @Override /** Dodaje krawędź do grafu */
  public boolean addEdge(int u, int v) {
    return addEdge(new Edge(u, v));
  }
  
  @Override /** Generuje drzewo DFS zaczynające się od wierzchołka v */
  /** Omówienie w podrozdziale 28.7 */
  public SearchTree dfs(int v) {
    List<Integer> searchOrder = new ArrayList<>();
    int[] parent = new int[vertices.size()];
    for (int i = 0; i < parent.length; i++)
      parent[i] = -1; // Inicjowanie elementu parent[i] wartością −1

    // Oznaczanie odwiedzonych wierzchołków
    boolean[] isVisited = new boolean[vertices.size()];

    // Rekurencyjne wyszukiwanie
    dfs(v, parent, searchOrder, isVisited);

    // Zwraca drzewo wyszukiwania
    return new SearchTree(v, parent, searchOrder);
  }

  /** Rekurencyjna metoda do wyszukiwania DFS */
  private void dfs(int v, int[] parent, List<Integer> searchOrder,
      boolean[] isVisited) {
    // Zapisywanie odwiedzonego wierzchołka
    searchOrder.add(v);
    isVisited[v] = true; // Wierzchołek v został odwiedzony

    for (Edge e : neighbors.get(v)) { // e.u to v 
      int w = e.v; // Na listingu 28.8 e.v to w
      if (!isVisited[w]) { 
        parent[w] = v; // Rodzicem wierzchołka w jest v
        dfs(w, parent, searchOrder, isVisited); // Wyszukiwanie rekurencyjne
      }
    }
  }

  @Override /** Rozpoczyna wyszukiwanie bfs od wierzchołka v */
  /** Omówienie w podrozdziale 28.9 */
  public SearchTree bfs(int v) {
    List<Integer> searchOrder = new ArrayList<>();
    int[] parent = new int[vertices.size()];
    for (int i = 0; i < parent.length; i++)
      parent[i] = -1; // Inicjowanie elementu parent[i] wartością –1

    java.util.LinkedList<Integer> queue =
      new java.util.LinkedList<>(); // Lista używana jako kolejka
    boolean[] isVisited = new boolean[vertices.size()];
    queue.offer(v); // Dodawanie v do kolejki
    isVisited[v] = true; // Oznaczanie wierzchołka jako odwiedzonego

    while (!queue.isEmpty()) {
      int u = queue.poll(); // Pobieranie z kolejki i zapis w u
      searchOrder.add(u); // u zostało sprawdzone
      for (Edge e: neighbors.get(u)) { // Zauważ, że e.u to u
        int w = e.v; // Na listingu 28.8 e.v to w 
        if (!isVisited[w]) { 
          queue.offer(w); // Dodawanie w do kolejki
          parent[w] = u; // Rodzicem w jest u
          isVisited[w] = true; // Oznaczanie wierzchołka jako odwiedzonego
        }
      }
    }

    return new SearchTree(v, parent, searchOrder);
  }

  /** Klasa wewnętrzna drzewa w klasie UnweightedGraph */
  /** Omówienie w podrozdziale 28.6 */
  public class SearchTree {
    private int root; // Korzeń drzewa
    private int[] parent; // Przechowuje rodzica każdego wierzchołka
    private List<Integer> searchOrder; // Przechowuje porządek przeszukiwania

    /** Tworzy drzewo na podstawie parametrów root, parent i searchOrder */
    public SearchTree(int root, int[] parent, 
        List<Integer> searchOrder) {
      this.root = root;
      this.parent = parent;
      this.searchOrder = searchOrder;
    }

    /** Zwraca korzeń drzewa */
    public int getRoot() {
      return root;
    }

    /** Zwraca rodzica wierzchołka v */
    public int getParent(int v) {
      return parent[v];
    }

    /** Zwraca listę reprezentującą porządek wyszukiwania */
    public List<Integer> getSearchOrder() {
      return searchOrder;
    }

    /** Zwraca liczbę znalezionych wierzchołków */
    public int getNumberOfVerticesFound() {
      return searchOrder.size();
    }
    
    /** Zwraca ścieżkę wierzchołków od danego wierzchołka do korzenia */
    public List<V> getPath(int index) {
      ArrayList<V> path = new ArrayList<>();

      do {
        path.add(vertices.get(index));
        index = parent[index];
      }
      while (index != -1);

      return path;
    }

    /** Wyświetla ścieżkę od korzenia do wierzchołka o podanym indeksie */
    public void printPath(int index) {
      List<V> path = getPath(index);
      System.out.print("Ścieżka z " + vertices.get(root) + " do " +
        vertices.get(index) + ": ");
      for (int i = path.size() - 1; i >= 0; i--)
        System.out.print(path.get(i) + " ");
    }

    /** Wyświetla całe drzewo */
    public void printTree() {
      System.out.println("Korzeń: " + vertices.get(root));
      System.out.print("Krawędzie: ");
      for (int i = 0; i < parent.length; i++) {
        if (parent[i] != -1) {
          // Wyświetlanie krawędzi
          System.out.print("(" + vertices.get(parent[i]) + ", " +
            vertices.get(i) + ") ");
        }
      }
      System.out.println();
    }
  }
  
  @Override /** Usuwa wierzchołek v; po udanym wykonaniu operacji zwraca true */ 
  public boolean remove(V v) {
    return true; // Implementację potraktuj jako ćwiczenie
  }

  @Override /** Usuwa krawędź (u, v); po udanym wykonaniu operacji zwraca true */
  public boolean remove(int u, int v) {
    return true; // Implementację potraktuj jako ćwiczenie
  }
}
