Simplified cycle detection via bfs

import java.util.*;

class Pair<Key, Value>{

    public Key first;

    public Value second;

    public Pair(Key first, Value second)

    {

        this.first=first;

        this.second=second;

    }

}

public class Main

{

    public static void main(String[] args) {

        System.out.println("Hello World");

        ArrayList<Integer> arr = new ArrayList<>();

        HashMap<Integer, ArrayList<Integer>> adj = makeAdjList(10,arr);

        addEdge(0,1,adj);

        addEdge(0,2,adj);

        addEdge(1,3,adj);

        addEdge(2,3,adj);

        addEdge(0,2,adj);

        addEdge(3,4,adj);

        addEdge(3,5,adj);

        addEdge(4,6,adj);

        addEdge(4,7,adj);

        addEdge(5,8,adj);

        addEdge(5,9,adj);

        addEdge(6,10,adj);

        addEdge(7,10,adj);

        addEdge(8,10,adj);

        addEdge(9,10,adj);

        System.out.println(adj);

        bfs(0,adj);

        System.out.println("Given graph contains cycle or not: true/false ?");

        System.out.println(isCycle(10,adj));

    }

   

    // Make adjList

    public static HashMap<Integer, ArrayList<Integer>> makeAdjList(int V, ArrayList<Integer> arr) {

        HashMap<Integer, ArrayList<Integer>> adj = new HashMap<>();

        for(int i=0;i<V+1;i++)

        {

            adj.put(i,new ArrayList<Integer>()) ;

        }

        return adj;

    }

   

    // Add Edge

    public static void addEdge(int src, int dest, HashMap<Integer, ArrayList<Integer>> adjList)

    {

        adjList.get(src).add(dest);

        adjList.get(dest).add(src);

    }

   

    // BFS traversal

    public static void bfs(int start, HashMap<Integer, ArrayList<Integer>> adjList)

    {

        ArrayList<Integer> ans = new ArrayList<>();

        int V = adjList.size();

        boolean vis[] = new boolean[V];

        Arrays.fill(vis,false);

        Queue<Integer> q = new LinkedList<>();

        q.add(0);

        vis[0]=true;

        while(!q.isEmpty())

        {

            int node=q.poll();

            ans.add(node);

            for(int it: adjList.get(node))

            {

                if(vis[it]==false)

                {

                    vis[it]=true;

                    q.add(it);

                }

            }

        }

        System.out.println(ans);

    }

   

    // Cycle detection in a graph via bfs traversal

    public static boolean checkCycle(int src, boolean vis[], int V, HashMap<Integer, ArrayList<Integer>> adjList)

    {

        //boolean vis[] = new boolean[V+1];

        //Arrays.fill(vis,false);

         Queue<Pair<Integer,Integer>> q = new LinkedList<>();

         q.add(new Pair(src,-1));

         vis[src]=true;

         while(!q.isEmpty())

         {

             int node=q.peek().first;

             int parent=q.peek().second;

             q.poll();

             for(int it: adjList.get(node))

             {

                 if(vis[it]==false)

                 {

                     vis[it]=true;

                     q.add(new Pair(it,node));

                 }

                 else if(parent!=it) return true;

             }

         }

         return false;

    }

   

    // Main cycle detection function using above

    public static boolean isCycle(int V, HashMap<Integer, ArrayList<Integer>> adjList)

    {

        boolean vis[] = new boolean[V+1];

        Arrays.fill(vis,false);

        for(int i=0;i<V;i++)

        {

            if(vis[i]==false)

            {

                if(checkCycle(i,vis,V,adjList)) return true;

            }

        }

        return false;

    }

}