class Solution {
public:
    void dfs(vector<vector<int>>& image, int i, int j,int val, int newColor)
    {
        if(i<0 || i>=image.size() || j<0 || j>= image[0].size() || image[i][j] == newColor || image[i][j] != val)
        {
            return;
        }
        image[i][j] = newColor;
        dfs(image,i-1,j,val,newColor);
        dfs(image,i+1,j,val,newColor);
        dfs(image,i,j-1,val,newColor);
        dfs(image,i,j+1,val,newColor);
    }
    
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor)
    {
        int val = image[sr][sc];
        dfs(image,sr,sc,val,newColor);
        return image;
    }
};

class Solution {
public:
   
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor)
    {
        // vector<vector<bool>> isPainted(image.size(), vector<bool>(image[0].size(), false));
        int oldColor=image[sr][sc];
        if(oldColor == newColor) return image;
        
        queue<pair<int,int>> q;
        int m= image.size();
        int n=image[0].size();
       
        q.push({sr,sc});
        // isPainted[sr][sc]=true;
        image[sr][sc]=newColor;
         int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}}; // up  
        
        
        while(q.empty()==false)
        {
            int currx=q.front().first;
            int curry=q.front().second;
            
            q.pop();
            
            // explore all directions
            for(int i=0 ; i<=3;i++)
            {       int nx= currx+dir[i][0];
                    int ny =curry+dir[i][1];
                if(nx>=0 && ny >= 0 && nx <m  && ny<n && image[nx][ny]==oldColor )
                {
                  
                    image[nx][ny]=newColor;
                    q.push({nx,ny});
                }
            }
           
        }
        return image;
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    // dfs(grid,i,j);
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    void dfs(vector<vector<char>>& grid, int i, int j) {

        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != '1')
            return;

        grid[i][j] = '0';

        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }

    void bfs(vector<vector<char>>& grid, int i, int j) {
        queue<pair<int, int>> q;
        q.push({i, j});
        int dx[] = {1, -1, 0, 0};
        int dy[] = {0, 0, 1, -1};
        while (q.empty() == false) {
            auto [r, c] = q.front();
            q.pop();

            // mark grid visited
            grid[i][j] = 'x';

            for (int k = 0; k < 4; k++) {
                int row_dash = r + dx[k];
                int col_dash = c + dy[k];
                if (row_dash >= 0 && col_dash >= 0 && row_dash < grid.size() &&
                    col_dash < grid[0].size() && grid[row_dash][col_dash] == '1') {
                    grid[row_dash][col_dash] = 'x';
                    q.push({row_dash, col_dash});
                }
            }
        }
    }
};

class Solution {
public:
    int m, n;
    int islandPerimeter(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    return dfs(grid, i, j);
                }
            }
        }
        return 0;
    }
    int dfs(vector<vector<int>>& grid, int i, int j) {
        // stores the count of edges of this block + its neighbours

        if (i < 0 || i > m - 1 || j < 0 || j > n - 1)
            return 1;
        if (grid[i][j] == -1)
            return 0;
        if (grid[i][j] == 0)
            return 1;

        grid[i][j] = -1;
        int count = 0;
        // Now we have counted the edges for current cell we proceed for dfs
        count += dfs(grid, i - 1, j);
        count += dfs(grid, i + 1, j);
        count += dfs(grid, i, j - 1);
        count += dfs(grid, i, j + 1);
        return count;
    }
};

class Solution {
public:
    int m, n;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j); // dfs will calculate area
                    ans = max(ans, area);
                }
            }
        }
        return ans;
    }

    int dfs(vector<vector<int>>& grid, int i, int j) {
        // safety check
        if (i < 0 || j < 0 || i > m - 1 || j > n - 1 || grid[i][j] == 0)
            return 0;
        grid[i][j] = 0;
        int left = dfs(grid, i - 1, j);
        int right = dfs(grid, i + 1, j);
        int up = dfs(grid, i, j - 1);
        int down = dfs(grid, i, j + 1);

        return 1 + left + right + up + down;
    }
};

class Solution {
public:
    int m, n;
    int closedIsland(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int count = 0;
        for (int i = 0; i < m ; i++) {
            for (int j = 0; j < n ; j++) {
                if (grid[i][j] == 0) {
                    if (dfs(grid, i, j) == true)
                        count++;
                }
            }
        }
        return count;
    }

    bool dfs(vector<vector<int>>& grid, int i, int j) {
        // if boundary crossed return false as island not closed
        if (i == -1 || j == -1 || i == m  || j == n )
            return false;
        if (grid[i][j]==1)
            return true;
        grid[i][j] = 1;
        bool left = dfs(grid, i - 1, j);
        bool right = dfs(grid, i + 1, j);
        bool up = dfs(grid, i, j - 1);
        bool down = dfs(grid, i, j + 1);

        return left && right && up && down;
    }
};

class Solution {
public:
    int m, n;
    vector<vector<int>> colorBorder(vector<vector<int>>& image, int sr, int sc,int color) {
        m = image.size();
        n = image[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));//
        int hunt = image[sr][sc];
        dfs(sr, sc, image, vis, hunt, color);
        return image;
    }
    void dfs(int i, int j, vector<vector<int>>& image,vector<vector<bool>>& vis, int curr_color, int color){

        if (i < 0 || j < 0 || i >= m || j >= n || vis[i][j] || image[i][j] != curr_color)
            return;

        vis[i][j] = true;
		//check if boundary then color the curr node
        if (i == 0 || j == 0 || i >= m - 1 || j >= n - 1) 
            image[i][j] = color;
        
        if ((i + 1 <= m - 1 && image[i + 1][j] != curr_color && !vis[i + 1][j]) ||
            (i - 1 >= 0 && image[i - 1][j] != curr_color && !vis[i - 1][j]) ||
            (j + 1 <= n - 1 && image[i][j + 1] != curr_color && !vis[i][j + 1]) ||
            (j - 1 >= 0 && image[i][j - 1] != curr_color && !vis[i][j - 1]))
            image[i][j] = color;
        dfs(i + 1, j, image, vis, curr_color, color);
        dfs(i - 1, j, image, vis, curr_color, color);
        dfs(i, j + 1, image, vis, curr_color, color);
        dfs(i, j - 1, image, vis, curr_color, color);
    }
};

vector<int>adj[n];
 for(int i=0;i<mat.size();i++){
            adj[mat[i][1]].push_back(mat[i][0]);
        }

vector<int>adj[n];
 for(int i=0;i<mat.size();i++){
            adj[ mat[i][1] ].push_back(mat[i][0]);
			adj[ mat[i][0] ].push_back(mat[i][1]);
        }

/*LC 207 Course Schedule 
edges given as dependency of courses 
Return true if you can finish all courses. Otherwise, return false.*/
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& mat) {
        int n = numCourses;
        vector<int> adj[n];
        vector<int> indegree(n, 0);
        for (int i = 0; i < mat.size(); i++) {
            adj[mat[i][1]].push_back(mat[i][0]);
            indegree[mat[i][0]]++;
        }
        vector<int> visited;
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
                visited.push_back(i);
            }
        }
        while (q.empty() == false) {
            int x = q.front();
            q.pop();
            for (auto it : adj[x]) {
                if (--indegree[it] == 0) {
                    q.push(it);
                    visited.push_back(it);
                }
            }
        }
        if (visited.size() != n)
            return false;
        else
            return true;
    }
};

class Solution {
  private:
    bool dfs(int src , int parent , vector<int>adj[],vector<int>&vis){
        vis[src]=1;
        for(auto it : adj[src]){
            if(vis[it]==-1){
               if( dfs(it,src,adj,vis))
                return true;
            }
            else if(it!=parent)// vis[it]==1
                return true;
        }
        return false;// will reach here if no cycle found
    }
  public:
    // Function to detect cycle in an undirected graph.
    bool isCycle(int V, vector<int> adj[]) {
        // Code here
        vector<int>vis(V,-1);
        
        for(int i=0;i<V;i++){
            if(vis[i]==-1 && dfs(i,-1,adj,vis))
                return true;//cycle found
        }
        return false;
    }
};

class Solution {
  public:
    // Function to detect cycle in an undirected graph.
    // bass neighbour parent na ho warna diqqat ho skti hai
    
    bool bfs(int src, vector<int> adj[] , vector<int>&vis)
    {
        
      queue<pair<int,int>>q;
      vis[src]=1;
      q.push({src,-1});
      
      while(!q.empty()){
          int node=q.front().first;
          int parent=q.front().second;
          q.pop();
          
          for(auto it:adj[node]){
              if(vis[it]==0){
                  vis[it]=1;
                  q.push({it,node});
              }
              else if(it!=parent)
                  return true;
          }
      }
      return false;
    }
    
    
    bool isCycle(int V, vector<int> adj[]) {
        // Code here
        vector<int>vis(V,0);
        for(int i=0;i<V;i++){
            if(vis[i]==0){
                if(bfs(i,adj,vis))
                    return true; // cycle found
            }
        }
        return false;
    }
};

class Solution
{
	public:
	//Function to find the shortest distance of all the vertices
    //from the source vertex S.
    typedef pair<int,int> P;
    vector <int> dijkstra(int V, vector<vector<int>> adj[], int S) {
        vector<int>vis(V,false);
        vector<int>dist(V,1e9);
        dist[S]=0;
        priority_queue<P,vector<P>,greater<P>>pq;//{cost,node}
        pq.push({0,S});
        while(!pq.empty()){
            int cost=pq.top().first;
            int u=pq.top().second;
            pq.pop();
            vis[u]=true;
            for(auto &it: adj[u]){
                int v=it[0];
                int w=it[1];
                if(vis[v]==false && dist[v]>dist[u]+w){
                    dist[v]=dist[u]+w;
                    pq.push({dist[v],v}); 
                }
            }
        }
        return dist;
    }
};

class Solution {
  public:
    /*  Function to implement Bellman Ford
    *   edges: vector of vectors which represents the graph
    *   S: source vertex to start traversing graph with
    *   V: number of vertices
    */
    vector<int> bellman_ford(int V, vector<vector<int>>& edges, int S) {
        // Code here
        vector<int>dist(V,1e8);
        dist[S]=0;
        for(int i=0;i<V-1;i++){
            for(auto &e : edges){
                int node=e[0];
                int adjNode=e[1];
                int wt=e[2];
                if(dist[node]!=1e8 && dist[node]+wt<dist[adjNode]){
                    dist[adjNode]=dist[node]+wt;
                }
            }
        }
        //check -ve cycle
        for(auto&e:edges){
            int node=e[0];
            int adjNode=e[1];
            int wt=e[2];
            if(dist[node]!=1e8 && dist[node]+wt<dist[adjNode] )
                return {-1};
        }
        return dist;
        
    }
};

class Solution {
public:
    // Function to find sum of weights of edges of the Minimum Spanning Tree.
    int spanningTree(int V, vector<vector<int>> adj[]) {
        vector<bool> visited(V, false); 
        vector<int> cost(V, INT_MAX);  // current minimum cost
        cost[0] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>,
                       greater<pair<int, int>>>
            pq;
        pq.push({cost[0], 0});
        int ans = 0;
        while (pq.empty() == false) {
            auto x = pq.top();
            int u = x.second;
            pq.pop();
            if (visited[u] == true)
                continue;
            visited[u] = true;
            ans = ans + x.first;
            for (auto it : adj[u]) {
                int v = it[0];
                int w = it[1];
                if (visited[v] == false && w < cost[v]) {
                    cost[v] = w;
                    pq.push({cost[v], v});
                }
            }
        }

        return ans;
    }
};