class Solution {
  /**
   * The recursive helper function that performs the depth-first search.
   * @param g the graph
   * @param prev the vertex via which we have reached the vertex u (can be null)
   * @param u the vertex we are currently visiting
   * @param known the vertexes that we have already visited
   */
  public static boolean componentHasCycle(Graph g, Vertex prev, Vertex u, Set<Vertex> known) {
    //if(prev != null && u.compareTo(prev) == 0);


    known.add(u);

    for(Vertex e : g.getNeighbours(u)) {
      if(known.contains(e)) {
        System.out.println("\nNode: " + u.getId() + " Node:" + e.getId());
        if(prev != null && prev.compareTo(e) == 0 && known.size() != g.getAllVertices().size()) return false;
        return true;
      }
      else {
        known.add(e);
        System.out.println("\nNode: " + e.getId());
        if(known.size() == g.getAllVertices().size()) return false;
        return componentHasCycle(g, u, e, known);
      }
    }
    return false;
  }

  public static int numCyclicComponents(Graph g) {
    Set<Vertex> known = new TreeSet<>();
    int cc = 0;

    for(Vertex e : g.getAllVertices()) {
      if(known.size() == g.getAllVertices().size()) return cc;
      System.out.print("k: " + known.size() + " v: " + g.getAllVertices().size() + " c: " + cc);
      Vertex prev = (e.getId() == 0) ? null : g.getVertexById(e.getId() - 1);
      if(componentHasCycle(g, prev, e, known)) cc++;
      System.out.println("k: " + known.size() + " v: " + g.getAllVertices().size() + " c: " + cc);
    }
    return cc;
  }
}