class Solution {
  /**
   * Counts the number of vertices in the same connected component as v in graph g.
   * This is done using depth first search.
   *
   * Returns 0 if the graph or vertex is null
   *
   * @param g
   *     The graph to count vertices in.
   * @param v
   *     The vertex to start counting at.
   * @return the number of vertices in the same connected component.
   */
  public static int countVertices(Graph g, Graph.Vertex v) {
    if(g == null || v == null) return 0;

    Set<Graph.Vertex> visited = new HashSet<>();
    Stack<Graph.Vertex> stack = new Stack<>();
    int vertices = 0;
    Graph.Vertex vertex = v;
    stack.push(vertex);

    while(!stack.empty()){
      visited.add(vertex);
      List<Graph.Vertex> neighbours = g.getNeighbours(vertex);
      for(Graph.Vertex vrtx : neighbours){
        if(!visited.contains(vrtx)){
          stack.push(vrtx);
        }
      }
      vertex = stack.pop();
      vertices++;
    }
    return vertices;
  }
}