Untitled

import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Queue;
import java.util.*;
class Graph {
    public boolean isSimilar(String s, String t){
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) != t.charAt(i)){
                return false;
            }
        }

        return s.length() == t.length();
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        LinkedList<String> que = new LinkedList<>();
        HashSet<String> words = new HashSet<>();

        for(String s: wordList){
            words.add(s);
        }

        que.addLast(beginWord);
        int level = 0;

        while(que.size()>0){
            int s = que.size();
            while(s-- > 0){
                String lw = que.removeFirst();

                for(String str: wordList){
                    if(words.contains(str) && isSimilar(str,lw)){
                        if(str.equals(endWord)) return level;
                        que.addLast(str);
                        words.remove(str);
                    }
                }
            }
            level++;
        }

        return -1;
    }
    // BFS 
    public int orangesRotting(int[][] grid) {
        int freshOranges = 0;
        Queue<Integer> que = new LinkedList<>();

        int n = grid.length;
        int m = grid[0].length;

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(grid[i][j] == 1){
                    freshOranges++;
                } else if(grid[i][j] == 2){
                    que.add(i*m+j);
                }
            }
        }

        if(freshOranges == 0) return 0;

        int level = 0;
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};

        while(que.size()>0){
            int size = que.size();

            while(size > 0){
                int rottenOrangeCell = que.remove();
                int i = rottenOrangeCell / m;
                int j = rottenOrangeCell % m;

                for(int[] dir: dirs){
                    int newRow = i + dir[0];
                    int newCol = j + dir[1];

                    if(newRow >=0 && newCol>=0 && newRow<n && newCol<m && grid[newRow][newCol] == 1){
                        grid[newRow][newCol] = 2;
                        freshOranges--;
                        que.add(newRow*m + newCol);
                    }
                }
                size--;
            }
            level++;
        }

        if(freshOranges == 0){
            return level - 1;
        } 
        return -1;
    }

    public static void BFS(int src, ArrayList<Integer>[] graph){
        int N = graph.length;
        boolean[] vis = new boolean[N];
        Queue<Integer> que= new LinkedList<>();

        que.add(src);
        vis[src] = true;

        while(que.size()>0){
            int u = que.remove();

            System.out.println(u);
            ArrayList<Integer> nbrs = graph[u];
            for(int i=0; i<nbrs.size(); i++){
                int nbr = nbrs.get(i);
                if(vis[nbr] == false){
                    vis[nbr] = true;
                    que.add(nbr);
                }
            }   
        }
    }

    public static void BFS_cycle(int src, ArrayList<Integer>[] graph){
        int N = graph.length;
        boolean[] vis = new boolean[N];
        Queue<Integer> que= new LinkedList<>();

        que.add(src);

        while(que.size()>0){
            int u = que.remove();
            if(vis[u] == true){
                System.out.println("We have a cycle at " + u);
            }
            vis[u] = true; // marking visited at removal time

            // System.out.println(u);
            ArrayList<Integer> nbrs = graph[u];
            for(int i=0; i<nbrs.size(); i++){
                int nbr = nbrs.get(i);
                if(vis[nbr] == false){
                    que.add(nbr);
                }
            }   
        }
    }

    public static void BFS_level(int src, ArrayList<Integer>[] graph){
        int N = graph.length;
        boolean[] vis = new boolean[N];
        Queue<Integer> que= new LinkedList<>();

        que.add(src);
        vis[src] = true;
        int level = 0;

        while(que.size()>0){
            int size = que.size();
            System.out.println("Level is "+level+" --->");
            while(size > 0){
                int u = que.remove();
                ArrayList<Integer> nbrs = graph[u];
                for(int i=0; i<nbrs.size(); i++){
                    int nbr = nbrs.get(i);
                    if(vis[nbr] == false){
                        vis[nbr] = true;
                        System.out.print(nbr+", ");
                        que.add(nbr);
                    }
                } 
                size--;  
            }
            level++;
            System.out.println();     
        }
    }


    // Kosaraju Algo
    public static void dfsSCC(ArrayList<Integer>[] graph,int src, boolean[] vis, ArrayList<Integer> path){
        vis[src] = true;

        for(int nbr: graph[src]){
            if(!vis[nbr]){
                dfsSCC(graph,nbr,vis,path);
            }
        }

        path.add(src);
    }

    public static void dfsSCC2(ArrayList<Integer>[] rGraph,boolean[] vis, int src){
        vis[src] = true;

        for(int nbr: rGraph[src]){
            if(!vis[nbr]){
                dfsSCC2(rGraph,vis,nbr);
            }
        }
    }

    public static int findSCC(ArrayList<Integer>[] graph, int N){
        // find topological order 

        ArrayList<Integer> path = new ArrayList<>();
        boolean[] vis = new boolean[N];

        for(int i=0; i<N; i++){
            if(!vis[i]){
                dfsSCC(graph,i,vis,path);
            }
        }

        // reverse graph 
        ArrayList<Integer>[] rGraph = new ArrayList[N];
        for(int i=0; i<N; i++){
            rGraph[i] = new ArrayList<>();
        }

        for(int u=0; u<N; u++){
            for(int v: graph[u]){
                rGraph[v].add(u);
            }
        }

        // printGraph(graph,N);
        // printGraph(rGraph,N);

        int count = 0;
        vis = new boolean[N];

        for(int i = path.size()-1; i>=0; i--){
            int u = path.get(i);
            if(!vis[u]){
                dfsSCC2(rGraph,vis,u);
                count++;
            }
        }
        return count;
    }



























    // construction ===============
    public static void addEdge(ArrayList<Integer>[] graph,int u, int v){
        graph[u].add(v);
        // graph[v].add(u);
    }

    public static void printGraph(ArrayList<Integer>[] graph, int N){
        for(int i=0; i<N; i++){
            System.out.println(i + " -> " + graph[i]);
        }
    }

    public static void main(String[] args){
        int N = 9;
        ArrayList<Integer>[] graph = new ArrayList[N];

        for(int i=0; i<N; i++){
            graph[i] = new ArrayList<>();
        }

        addEdge(graph,0,1);
        addEdge(graph,1,2);
        addEdge(graph,2,0);
        addEdge(graph,2,3);
        addEdge(graph,3,4);
        addEdge(graph,4,7);
        addEdge(graph,7,6);
        addEdge(graph,7,8);
        addEdge(graph,6,8);
        addEdge(graph,6,5);
        addEdge(graph,5,4);

        System.out.println(findSCC(graph,N));
    }
}