Friday, 19 April 2024

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;
    }
}

No comments:

Post a Comment

Good thoughtful question on Binary search on answers

Problem link:  https://leetcode.com/problems/maximize-score-of-numbers-in-ranges/description/ Solution: //import java.util.Arrays; class So...