그래프

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    //we will use dfs for cloning the graph, we will traverse 
    //the graph in depth first search manner and create a complete clone of the given graph.

    public Node cloneGraph(Node node) {
        if(node == null) return node;

        Node clone = new Node(node.val);
        Node[] visited = new Node[101]; // 101 is the max size of nodes that can be present in the test case.
        dfs(clone,node,visited);
        return clone;

    }
    public void dfs(Node clone, Node actual, Node[] visited){
        visited[clone.val] = clone;
        for(Node next : actual.neighbors){
            if(visited[next.val] ==null) {
                Node newNode = new Node(next.val);
                clone.neighbors.add(newNode);
                dfs(newNode,next,visited);
            }
            else {
                clone.neighbors.add(visited[next.val]);
            }
        }
    }
}

// this is similar to finding cycle in a directed graph
//we have used kahn's topological sorting algo to check if the cycle exist in the graph or not.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i =0;i<numCourses;i++){
            graph.add(new ArrayList<>());
        }
        //getting indegrees of all the nodes
        int indegree[] = new int[numCourses];
        for(int i =0;i<prerequisites.length;i++){
            indegree[prerequisites[i][0]]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for(int i =0;i<numCourses;i++){
            if(indegree[i]==0) q.add(i);
        }
        // create adjacency matrix in ArrayList
         for(int i=0;i<prerequisites.length;i++){
            ArrayList<Integer> l2 = graph.get(prerequisites[i][1]);
            l2.add(prerequisites[i][0]);
            graph.set(prerequisites[i][1],l2);
        }

        int count =0;
        while(!q.isEmpty()){
            int node = q.remove();
            count++;
            for(Integer it : graph.get(node)){
                indegree[it]--;
                if(indegree[it] ==0) q.add(it);
            }
        }
       return count ==numCourses;
    }

}

import java.util.*;
public class Solution 
{
    public static ArrayList<Integer> topologicalSort(ArrayList<ArrayList<Integer>> edges, int v, int e) 
    {
        // we will use depth first search for getting the topo sort of the 
        //given graph.
        ArrayList<Integer> list = new ArrayList<>(); 
        // lets create an adjacency list of the given edges
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i =0;i<v;i++){
            graph.add(new ArrayList<>());
        }
        for(ArrayList<Integer> l: edges){
            ArrayList<Integer> temp = graph.get(l.get(0));
            temp.add(l.get(1));
            graph.set(l.get(0),temp);
        }
        /// lets call depth first search to get topo sort
        ///we will use stack data structure to get the nodes based
        Stack<Integer> s = new Stack<>();
        int visited[] = new int[v];

        for(int i=0;i<v;i++){
            if(visited[i] ==0) {
                getTopoSort(i,s,graph,visited);
            }
        }
        //now we will pop the stack to get the nodes in order of topo sort
        while(!s.isEmpty()){
            list.add(s.pop());
        }
        return list;
    }
    public static void getTopoSort(int n,Stack<Integer> s, ArrayList<ArrayList<Integer>> graph,int[] visited){
        visited[n]  = 1;
        for(Integer i: graph.get(n)){
            if(visited[i]==0){getTopoSort(i,s,graph,visited);}
        }
        s.push(n);
    }
} 

public class Solution 
{
    public static int getTotalIslands(int[][] mat) 
    {
        int count =0;
        for(int i =0;i<mat.length;i++){
            for(int j=0;j<mat[0].length;j++){
                if(mat[i][j]!=2 && mat[i][j] ==1){
                    traverseLand(mat,i,j);
                    count++;
                }
            }
        }
        return count;
    }
    public static void traverseLand(int [][] mat, int i,int j){
        if(i<0 || j<0 || i>=mat.length || j>=mat[0].length || mat[i][j] ==0 ||
           mat[i][j] ==2) return;
        mat[i][j] =2;
        //left, right,top and bottom movements
        traverseLand(mat,i,j-1);
        traverseLand(mat,i,j+1);
        traverseLand(mat,i-1,j);
        traverseLand(mat,i+1,j);
        //diagonal movements
        traverseLand(mat,i-1,j-1);
        traverseLand(mat,i+1,j+1);
        traverseLand(mat,i-1,j+1);
        traverseLand(mat,i+1,j-1);
    }
}

class Solution
{
    public boolean isBipartite(int V, ArrayList<ArrayList<Integer>>adj)
    {
        //we will use breadh first search for finding out if a graph is bipartite or
        //not
        //a graph is called as bipartite graph if two adjacent nodes can be colored with
        //different colors
        int color[]= new int[V];
        Arrays.fill(color,-1);//intialize all the color of all the nodes as 0;
        for(int i =0;i<V;i++){
            if(color[i]==-1){
                //we are taking 0 as first color of the node i
                color[i] = 0;
                if(!possibleDFS(color,i,adj)) return false;
            }
        }
        return true;
    }
    public boolean possibleBFS(int [] color, int i, ArrayList<ArrayList<Integer>> adj){
        Queue<Integer> q = new LinkedList<>();
        q.add(i);
        while(!q.isEmpty()){
            int node  = q.remove();
            for(Integer it : adj.get(node)){
                if(color[it]==-1){
                     q.add(it);
                     color[it]  = 1-color[node];
                }
                else if(color[it]==color[node]) return false;
            }

        }
     return true;
    }
    public boolean possibleDFS(int [] color, int i, ArrayList<ArrayList<Integer>>adj){

        for(Integer it : adj.get(i)){
            if(color[it] ==-1) {
                color[it] = 1-color[i];
                if(!possibleDFS(color,it,adj)) return false;
            }
            else if(color[it]==color[i]) return false;
        }
        return true;
    }
}