import java.util.*;
class Pair{
int first;int second;
Pair(int f, int s)
{
this.first=f; this.second=s;
}
}
public class DetectCycleViaBfs {
// Function to detect cycle in an undirected graph.
public boolean isCycle(int maxIntegerVertex, ArrayList<ArrayList<Integer>> adj) {
// Code here
Queue<Pair> q = new ArrayDeque<>();
int V=maxIntegerVertex;
boolean vis[] = new boolean[V];
Arrays.fill(vis,false);
// code to find detect cycle in connected component
for(int i=0;i<V;i++)
{
if(!vis[i])
if(checkForCycle(adj, i,vis,q))
return true;
}
return false; //NO CYCLE
}
//check for cycle using bfs
public static boolean checkForCycle(ArrayList<ArrayList<Integer>> adj, int s,
boolean vis[], Queue<Pair> q)
{
q.add(new Pair(s, -1)); //FOR STARTING NODE
vis[s] =true;
// until the queue is empty
while(!q.isEmpty())
{
// source node and its parent node
int node = q.peek().first;
int par = q.peek().second; //PARENT
q.remove();
// go to all the adjacent nodes
for(Integer it: adj.get(node))
{
if(!vis[it])
{
q.add(new Pair(it, node));
vis[it] = true;
}
// if adjacent node is visited and is not its own parent node
else if(par != it) return true; //cycle detection
}
}
return false;
}
}
