Q17 Minimum edges(0-1 BFS) | Practice | GeeksforGeeks

//{ Driver Code Starts
import java.io.*;
import java.util.*;


class IntArray
{
    public static int[] input(BufferedReader br, int n) throws IOException
    {
        String[] s = br.readLine().trim().split(" ");
        int[] a = new int[n];
        for(int i = 0; i < n; i++)
            a[i] = Integer.parseInt(s[i]);
        
        return a;
    }
    
    public static void print(int[] a)
    {
        for(int e : a)
            System.out.print(e + " ");
        System.out.println();
    }
    
    public static void print(ArrayList<Integer> a)
    {
        for(int e : a)
            System.out.print(e + " ");
        System.out.println();
    }
}


class IntMatrix
{
    public static int[][] input(BufferedReader br, int n, int m) throws IOException
    {
        int[][] mat = new int[n][];
        
        for(int i = 0; i < n; i++)
        {
            String[] s = br.readLine().trim().split(" ");
            mat[i] = new int[s.length];
            for(int j = 0; j < s.length; j++)
                mat[i][j] = Integer.parseInt(s[j]);
        }
        
        return mat;
    }
    
    public static void print(int[][] m)
    {
        for(var a : m)
        {
            for(int e : a)
                System.out.print(e + " ");
            System.out.println();
        }
    }
    
    public static void print(ArrayList<ArrayList<Integer>> m)
    {
        for(var a : m)
        {
            for(int e : a)
                System.out.print(e + " ");
            System.out.println();
        }
    }
}

class GFG {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t;
        t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            
            int[] a = new int[2];
            String s[] = br.readLine().trim().split(" ");
            if(s.length == 2){
                a[0] = Integer.parseInt(s[0]);
                a[1] = Integer.parseInt(s[1]);
            } else{
                a[0] = Integer.parseInt(s[0]);
                s = br.readLine().trim().split(" ");
                a[1] = Integer.parseInt(s[0]);
            }
            int[][] edges = IntMatrix.input(br, a[1], 2);
            
            
            int src; 
            src = Integer.parseInt(br.readLine());
            
            
            int dst; 
            dst = Integer.parseInt(br.readLine());
            
            Solution obj = new Solution();
            int res = obj.minimumEdgeReversal(edges, a[0], a[1], src, dst);
            
            System.out.println(res);
            
        }
    }
}

// } Driver Code Ends


class Solution {
    public static int minimumEdgeReversal(int[][] edges, int n, int m, int src, int dst) {
        //taking input
        ArrayList<ArrayList<pair>> graph = new ArrayList<>();
        for(int i = 0 ;i < n ; i++)
        graph.add(new ArrayList<>());
        
        for(int edge[] : edges){
            //making into 0 based indexing
            graph.get(edge[0]-1).add(new pair(edge[1]-1,0));
            graph.get(edge[1]-1).add(new pair(edge[0]-1,1));
        }
        
        boolean visited[] = new boolean[n];
        
        /* now using 0-1 bfs , we just replaec PQ with linkedlist and make 2 partion
        as there are just 2 weights in the graph , +0 edges are added in the
        front and +1 are added in the end , makes complexity O(E+V)
        */
        LinkedList<pair> q = new LinkedList<>();
        q.addLast(new pair(src-1 , 0));
        
        while(q.size() > 0){
            pair rem = q.removeFirst();
            int vtx = rem.vtx , wt = rem.wt;
            
            visited[vtx] = true;
            
            if(vtx == dst-1)
            return wt;
            
            for(pair edge : graph.get(vtx)){
                
                if(visited[edge.vtx] == false){
                    if(edge.wt == 0)
                    q.addFirst(new pair(edge.vtx , wt + 0));
                    
                    else
                    q.addLast(new pair(edge.vtx , wt + 1));
                }
            }
            
        }
        return - 1;
    }
    
    public static class pair implements Comparable<pair>{
        int vtx , wt; 
        
        pair(int vtx , int wt){
            this.vtx = vtx;
            this.wt = wt;
        }
        
        public int compareTo(pair o){
            return this.wt - o.wt;
        }
    }
}