Saturday 20 April 2024

Detect a cycle in an undirected graph using dfs

import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello World");
        int V = 5;  // Adjust the number of vertices appropriately
        HashMap<Integer, ArrayList<Integer>> adj = makeAdjList(V);
        addEdge(0, 2, adj);
        addEdge(0, 1, adj);
        addEdge(0, 3, adj);
        addEdge(2, 4, adj);
        addEdge(4, 1, adj);
       
        System.out.println(adj);
        System.out.println("The graph has cycle: " + isCycle(V, adj));
    }

    public static boolean dfs(int node, int parent, HashMap<Integer,
ArrayList<Integer>> adj, boolean[] vis) {
        vis[node] = true;
        for (int it : adj.get(node)) {
            if (!vis[it]) {
                if (dfs(it, node, adj, vis)) {
                    return true;
                }
            } else if (it != parent) {
                return true;
            }
        }
        return false;
    }

    public static boolean isCycle(int V, HashMap<Integer,
ArrayList<Integer>> adj) {
        boolean[] vis = new boolean[V];
        for (int i = 0; i < V; i++) {
            if (!vis[i]) {
                if (dfs(i, -1, adj, vis)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static HashMap<Integer, ArrayList<Integer>>
makeAdjList(int V) {
        HashMap<Integer, ArrayList<Integer>> adj = new HashMap<>();
        for (int i = 0; i < V; i++) {
            adj.put(i, new ArrayList<Integer>());
        }
        return adj;
    }

    public static void addEdge(int src, int dest,
HashMap<Integer, ArrayList<Integer>> adjList) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }
}

 

at No comments:

Friday 19 April 2024

Simplified dfs traversal in a graph

import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello World");
        int V = 9;  // Total number of vertices (0 to 8)
        HashMap<Integer, ArrayList<Integer>> adj = makeAdjList(V);
        addEdge(0, 2, adj);
        addEdge(0, 1, adj);
        addEdge(2, 0, adj);
        addEdge(2, 4, adj);
        addEdge(1, 0, adj);
        addEdge(3, 0, adj);
        addEdge(4, 2, adj);
        addEdge(0, 3, adj);
        System.out.println(adj);
        boolean[] vis = new boolean[V];
        List<Integer> ans = new ArrayList<>();
        dfs(0, adj, vis, ans);
        System.out.println("The dfs traversal of the graph is:");
        System.out.println(ans);
    }

    // DFS of graph
    public static void dfs(int src, HashMap<Integer, ArrayList<Integer>> adj, boolean[] vis, List<Integer> ans) {
        vis[src] = true;
        ans.add(src);
        for (int it : adj.get(src)) {
            if (!vis[it]) {
                dfs(it, adj, vis, ans);
            }
        }
    }

    // Make adjList
    public static HashMap<Integer, ArrayList<Integer>> makeAdjList(int V) {
        HashMap<Integer, ArrayList<Integer>> adj = new HashMap<>();
        for (int i = 0; i < V; 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);
    }
}

 

at No comments:

Shortest path in undirected graph with unit weight starting from start node 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(8,arr);
        addEdge(0,1,adj);
        addEdge(0,3,adj);
        addEdge(1,3,adj);
        addEdge(1,2,adj);
        addEdge(3,4,adj);
        addEdge(4,5,adj);
        addEdge(5,6,adj);
        addEdge(2,6,adj);
        addEdge(6,7,adj);
        addEdge(6,8,adj);
        addEdge(7,8,adj);
       
        System.out.println(adj);
        bfs(0,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)
    {
        int V = adjList.size();
        int dist[] = new int[V];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[0]=0;
        Queue<Pair<Integer,Integer>> q = new LinkedList<>();
        q.add(new Pair(0,0));
        while(!q.isEmpty())
        {
            int node=q.peek().first;
            int distance_node = q.peek().second;
            q.poll();
            for(int it: adjList.get(node))
            {
                if(distance_node + 1 < dist[it])
                {
                    dist[it]=distance_node + 1;
                    q.add(new Pair(it,distance_node + 1));
                }
            }
        }
        for(int it: dist)
        {
            System.out.print(it +" ");
        }
    }
}

at No comments:

BFS Q1) Level of nodes

Problem link: https://www.geeksforgeeks.org/problems/level-of-nodes-1587115620/1 

class Solution
{
    //Function to find the level of node X.
    int nodeLevel(int V, ArrayList<ArrayList<Integer>> adj, int x) {
        int ans = -1;
        boolean[] vis = new boolean[V];
        Arrays.fill(vis, false);
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        vis[0] = true;
        boolean fg = false;
        while (!q.isEmpty()) {
            int size = q.size();
            ans++; // Increment level for each level of nodes
            for (int i = 0; i < size; i++) {
                int node = q.poll();
                if (node == x) return ans; // If the target node is found, return its level
                for (int it : adj.get(node)) {
                    if (!vis[it]) {
                        vis[it] = true;
                        q.add(it);
                    }
                }
            }
        }
        return -1; // Return -1 if the target node is not found
    }
   
}
at No comments:

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

at No comments:

Simplified bfs traversal in a graph

import java.util.*;
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(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);
    }
   
    // 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);
    }
}

at No comments:

Simplified Make adjacency list and add edge in graph

import java.util.*;
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(3,arr);
        addEdge(0,1,adj);
        addEdge(1,3,adj);
        addEdge(2,3,adj);
        addEdge(0,2,adj);
        System.out.println(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);
    }
}

at No comments:

Cycle detection in Graph 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");
        HashMap<Integer, ArrayList<Integer>> adjList = new HashMap<>();

        // Adding nodes to the graph
        for (int i = 0; i <= 8; i++) {
            adjList.put(i, new ArrayList<>());
        }

        // Adding edges to the graph
        addEdge(adjList, 1, 2);
        addEdge(adjList, 1, 3);
        addEdge(adjList, 3, 4);
        addEdge(adjList, 3, 6);
        addEdge(adjList, 6, 8);
        addEdge(adjList, 7, 5);
        addEdge(adjList, 2, 5);

        // Print the adjacency list
        System.out.println("Adjacency List: " + adjList);
        System.out.println("The graph has cycle: true/false ?");
        //ArrayList < Integer > ans = bfsOfGraph(7, adjList);
        //int n = ans.size();
        /*for(int i = 0;i<n;i++) {
            //System.out.print(ans.get(i)+" ");
           
        }*/
        System.out.println(isCycle(8,adjList));
    }
   
    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(bfsOfGraph(i, vis, V,adjList)) return true;
            }
        }
        return false;
    }
   
    public static boolean bfsOfGraph(int src, boolean vis[], int V, HashMap<Integer, ArrayList<Integer>> adjList) { // V is last number(max num) of graph
        //ArrayList < Integer > bfs = new ArrayList < > ();
        //boolean vis[] = new boolean[V+1];
        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();
            //bfs.add(node);
            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;
    }
   
   
    // Helper method to add an edge to the graph
    public static void addEdge(HashMap<Integer, ArrayList<Integer>> adjList, int source, int destination) {
        adjList.get(source).add(destination);
        adjList.get(destination).add(source); // If the graph is undirected
    }
}

at No comments:

BFS traversal of graph represented by adjacency list

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        System.out.println("Hello World");
        HashMap<Integer, ArrayList<Integer>> adjList = new HashMap<>();

        // Adding nodes to the graph
        for (int i = 0; i <= 9; i++) {
            adjList.put(i, new ArrayList<>());
        }

        // Adding edges to the graph
        addEdge(adjList, 0, 1);
        addEdge(adjList, 1, 2);
        addEdge(adjList, 1, 6);
        addEdge(adjList, 2, 3);
        addEdge(adjList, 2, 4);
        addEdge(adjList, 6, 7);
        addEdge(adjList, 4, 5);
        addEdge(adjList, 6, 9);
        addEdge(adjList, 7, 8);

        // Print the adjacency list
        System.out.println("Adjacency List: " + adjList);
        System.out.println("The bfs traversal is:");
        ArrayList < Integer > ans = bfsOfGraph(9, adjList);
        int n = ans.size();
        for(int i = 0;i<n;i++) {
            System.out.print(ans.get(i)+" ");
        }
    }
    public static ArrayList<Integer> bfsOfGraph(int V, HashMap<Integer, ArrayList<Integer>> adjList) { // V is last number(max num) of graph
        ArrayList < Integer > bfs = new ArrayList < > ();
        boolean vis[] = new boolean[V+1];
        Queue < Integer > q = new LinkedList < > ();
        q.add(0);
        vis[0] = true;
        while (!q.isEmpty()) {
            int node = q.poll();
            bfs.add(node);
            for (int it: adjList.get(node)) {
                if (vis[it] == false) {
                    vis[it] = true;
                    q.add(it);
                }
            }
        }

        return bfs;
    }
   
   
    // Helper method to add an edge to the graph
    public static void addEdge(HashMap<Integer, ArrayList<Integer>> adjList, int source, int destination) {
        adjList.get(source).add(destination);
        adjList.get(destination).add(source); // If the graph is undirected
    }
}

at No comments:

Wednesday 17 April 2024

Count inversion in an array, O(nlogn) approach

import java.util.*;

public class Main {

    private static int merge(int[] arr, int low, int mid, int high) {
        ArrayList<Integer> temp = new ArrayList<>(); // temporary array
        int left = low;      // starting index of left half of arr
        int right = mid + 1;   // starting index of right half of arr

        //Modification 1: cnt variable to count the pairs:
        int cnt = 0;

        //storing elements in the temporary array in a sorted manner//

        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp.add(arr[left]);
                left++;
            } else {
                temp.add(arr[right]);
                cnt += (mid - left + 1); //Modification 2
                right++;
            }
        }

        // if elements on the left half are still left //

        while (left <= mid) {
            temp.add(arr[left]);
            left++;
        }

        //  if elements on the right half are still left //
        while (right <= high) {
            temp.add(arr[right]);
            right++;
        }

        // transfering all elements from temporary to arr //
        for (int i = low; i <= high; i++) {
            arr[i] = temp.get(i - low);
        }
        return cnt; // Modification 3
    }

    public static int mergeSort(int[] arr, int low, int high) {
        int cnt = 0;
        if (low >= high) return cnt;
        int mid = (low + high) / 2 ;
        cnt += mergeSort(arr, low, mid);  // left half
        cnt += mergeSort(arr, mid + 1, high); // right half
        cnt += merge(arr, low, mid, high);  // merging sorted halves
        return cnt;
    }

    public static int numberOfInversions(int[] a, int n) {
        // Count the number of pairs:
        return mergeSort(a, 0, n - 1);
    }


    public static void main(String[] args) {
        //int[] a = {5, 4, 3, 2, 1};
        //int n = 5;
        int[] a = {1,3,5,2,4,6};
        int n = 6;
        int cnt = numberOfInversions(a, n);
        System.out.println("The number of inversions are: " + cnt);
    }
}

 

at No comments:
Subscribe to: Posts (Atom)

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...

  • (no title)
     // Grid Unique Paths-->2-D dp concept(space optimised) // tc = O(mxn)  // sc = O(n) --> array import java.util.*; class dp {      pub...
  • (no title)
    // Grid Unique Paths-->2-D dp concept(Tabulation) // tc = O(mxn)  // sc = O(mxn) --> extra dp array import java.util.*; class dp {    ...
  • (no title)
     // Count Grid Unique Paths-->2-D dp concept(Memoization) // tc = O(mxn) -->at max there will be n*m calls of recursion // sc = O((n-1...