Detect Cycle in an undirected graph using Breadth First Search Algorithm

Question

Using this algorithm I am getting wrong answers but my testcases are giving correct answers. Let me know where I am going wrong. In this algorithm I have used Breadth First Search(BFS) technique to find to detect the cycle.

// Using bfs approach
class Solution{
    public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj){
        Queue<Integer> q=new LinkedList<>();
        boolean vis[]=new boolean[V];
        int parent[]=new int[V];
        parent[0]=-1;
        q.add(0);
        vis[0]=true;
        while(!q.isEmpty()){
            int cur=q.poll();
            for(int  i:adj.get(cur)){
                // if(vis[i]==true) return true;
                if(!vis[i]){
                    q.add(i);
                    parent[i]=cur;
                    vis[i]=true;
                }
                else if(parent[cur]!=i) return true;
            }
        }
        return false;
    }
}

Answer 1

Assumptions

The approach assumes that the input undirected graph is connected.

Please check whether it is a valid assumption for all possible inputs for the problem domain.

Possible solution

1. The existing method will work for a single forest
2. Add additional startNode and visited parameters to the existing method
3. Add another wrapper method that will call the existing method for every unvisited node(forest).

  boolean hasCycle(final int N, final List<List<Integer>> graph) {
    final boolean[] visited = boolean[N];

    for (int vertex = 0; vertex < N; vertex++) {
      if (!visited[vertex] && hasCycle(N, vertex, visited, graph)) {
        return true;
      }
    }

    return false;
  }

Both Methods

  boolean hasCycle(final int N, final int start, final boolean[] visited, final List<List<Integer>> graph) {
    visited[start] = true;

    final int parent[] = new int[N];
    parent[start] = -1;

    final Queue<Integer> q = new LinkedList<>();
    q.add(start);

    while(!q.isEmpty()) {
      final int node = q.poll();

      // assumes for nodes without edges, an empty list will be returned
      for(int adj : graph.get(node)) {
        if (!visited[adj]) {
          q.add(adj);
          parent[adj] = node;
          visited[adj] = true;
        } else if (parent[node] != adj) {
          return true;
        }
      }
    }

    return false;
  }

  boolean hasCycle(final int N, final List<List<Integer>> graph) {
    final boolean[] visited = boolean[N];

    for (int vertex = 0; vertex < N; vertex++) {
      if (!visited[vertex] && hasCycle(N, vertex, visited, graph)) {
        return true;
      }
    }

    return false;
  }

Disclaimer

This is untested and uncompiled code (typed in SO)