No of islands present can be improved further

 

class Solution {

  public:

    void DFS(int i ,int j,vector<vector<int>>&arr,int n,int m,int color){

        arr[i][j]=color;

        int dx[8]={1,1,1,0,0,-1,-1,-1};

        int dy[8]={0,-1,1,-1,1,-1,0,1};

        for(int k=0;k<8;k++){

            int r=i+dx[k];

            int c=j+dy[k];

            if(r>=0&&r<n&&c>=0&&c<m&&arr[r][c]==1){

                DFS(r,c,arr,n,m,color);

            }

            

        }

      /*  int rnxt=i+1;

        int rpre=i-1;

        int cnxt=j+1;

        int cpre=j-1;

       if(rnxt>=0&&rnxt<n){

            if(cnxt>=0&&cnxt<m&&arr[rnxt][cnxt]==1)DFS(rnxt,cnxt,arr,n,m,color);

            

            if(cpre>=0&&cpre<m&&arr[rnxt][cpre]==1)DFS(rnxt,cpre,arr,n,m,color);

            if(arr[rnxt][j]==1)DFS(rnxt,j,arr,n,m,color);

        }

        if(rpre>=0&&rpre<n){

            if(cnxt>=0&&cnxt<m&&arr[rpre][cnxt]==1)DFS(rpre,cnxt,arr,n,m,color);

            

            if(cpre>=0&&cpre<m&&arr[rpre][cpre]==1)DFS(rpre,cpre,arr,n,m,color);

            if(arr[rpre][j]==1)DFS(rpre,j,arr,n,m,color);

        }

        if(cnxt>=0&&cnxt<m&&arr[i][cnxt]==1)DFS(i,cnxt,arr,n,m,color);

        if(cpre>=0&&cpre<m&&arr[i][cpre]==1)DFS(i,cpre,arr,n,m,color);

        

         }*/

    }

    int countIslands(vector<vector<char>> grid) {

        // Code here

        int n=grid.size();

        int m=grid[0].size();

        vector<vector<int>>arr(n,vector<int>(m,0));

        for(int i=0;i<n;i++){

            for(int j=0;j<m;j++){

                if(grid[i][j]=='L'){

                    arr[i][j]=1;

                }else arr[i][j]=0;

            }

        }

        int color=2;

        for(int i=0;i<n;i++){

            

            for(int j=0;j<m;j++){

                if(arr[i][j]==1){

                    DFS(i,j,arr,n,m,color);

                    color++;

                }

                    

                

            }

        }

        int noc=0;

        unordered_map<int,int>mp;

        for(int i=0;i<n;i++){

            

            for(int j=0;j<m;j++){

                if(arr[i][j]){

                    if(!mp[arr[i][j]]){

                        noc++;

                        mp[arr[i][j]]=1;

                    }

                }

                    

                

            }

        }

        return noc;

        

        

    }

};

Biprariate Graph check correct approach soln (DFS)leetcode accepted (BEATS 100%)

 class Solution {

public:

    void DFS(int node,vector<vector<int>>&adj,vector<int>&colors,int cc){

        colors[node]=cc;

        for(int x:adj[node]){

            if(!colors[x])DFS(x,adj,colors,(cc==2)?1:2);

        }

    }

    bool isBipartite(vector<vector<int>>& graph) {

        int n =graph.size();

        vector<int>colors(n,0);

        for(int i =0;i<n;i++){

            if(!colors[i])DFS(i,graph,colors,2);

        }

        for(int i=0;i<n;i++){

            for(int x:graph[i]){

                if(colors[i]==colors[x])return false;

            }

        }

        return true;

    }

};

Biprariate Graph check coorect approach soln (BFS)leetcode accepted

   

    void BFS(vector<vector<int>>&adj,int node,vector<int>&colors){

        queue<int>q;

        int blue=1;

        int red=2;

     

        q.push(node);

        colors[node]=blue;

       

        while(!q.empty()){

            int x=q.front();

            q.pop();

            for(int y:adj[x]){

                if(!colors[y]){

                    q.push(y);

                    colors[y]=(colors[x]==blue)?red:blue;

                }

            }

         

        }

    }

    bool isBipartite(vector<vector<int>>& graph) {

         int n=graph.size();

         vector<int>colors(n,0);

         for(int i=0;i<n;i++){

            if(!colors[i])BFS(graph,i,colors);

         }

         for(int i=0;i<n;i++){

            for(int x:graph[i]){

                if(colors[i]==colors[x])return false;

            }

         }

         return true;

    }

checking Bipariate Graph in my Own Way time limit Exceeded in GFG(1114 /1119) passed

class Solution {

  public:

     bool checkneighbour(vector<int>&arr,vector<vector<int>>&adj,int item){

         for(int x:arr){

             for(int y:adj[x]){

                 if(y==item)return true;

             }

         }

         return false;

     }

     bool ans(vector<vector<int>>&adj,int V){

         queue<int>q;

         vector<int>one;

         vector<int>two;

         vector<int>visited(V,0);

         q.push(0);

         visited[0]=1;

         while(!q.empty()){

             int x=q.front();

             if(!checkneighbour(one,adj,x))one.push_back(x);

             else if(!checkneighbour(two,adj,x))two.push_back(x);

             else return false;

             q.pop();

             for(int y:adj[x] ){

                 if(!visited[y]){

                     q.push(y);

                     visited[y]=1;

                 };

             }

         }

         return true;

     }

    bool isBipartite(int V, vector<vector<int>> &edges) {

        // Code here

        vector<vector<int>> adj(V);

        for(auto& e : edges){

            adj[e[0]].push_back(e[1]);

            adj[e[1]].push_back(e[0]);

        }

        return ans(adj, V);

        

    }

};

check if a cycle exists usign kahn's Algo or Topological sort(Accpted soln in GFG)

 class Solution {

  public:

    vector<int> toposort(vector<vector<int>>&adj,int V){

        vector<int>count(V,0);

        queue<int>q;

        vector<int>visited;

        for(int i=0;i<V;i++){

            for(int x:adj[i]){

                count[x]++;

            }

        }

        for(int i=0;i<V;i++){ if(count[i]==0) q.push(i); }

        while(!q.empty()){

            int x=q.front();

            q.pop();

            visited.push_back(x);

            for(int y:adj[x]){

                count[y]--;

                if(count[y]==0)q.push(y);

           }

        }

        return visited;

    }

    bool isCyclic(int V, vector<vector<int>> &edges) {

        // code here

        vector<vector<int>> adj(V);

        for(auto& e : edges){

            adj[e[0]].push_back(e[1]);

        }

        vector<int>ans=toposort(adj,V);

        if(ans.size()==adj.size()) return false;

        else return true;

        

    }

};

kahn's algo of topological sort

TOPOLOGICAL SORING IS DONE ON DIRECTED ACYCLIC GRAPH (DAG) 

void kahnsalgo(){

       queue<int>q;

       vector<int>count=Count_indegree();

       for(int i=0;i<v;i++)if(count[i]==0)q.push(i);

       while(!q.empty()){

           int x=q.front();

           cout<<x<<" ";

           q.pop();

           for(int y:adj[x]){

               count[y]--;

               if(count[y]==0)q.push(y);

           }

           

       }

   }

detetct cycle in directed graph uncompleted

  void dfs(int node,vector<int>&path){

    if(!path[node])path[node]=1;

    else {

        cout<<"cycle detected";

        return;

        

    }

    for(int x: adj[node]){

        dfs(x,path);

    }

    path[node]=0;

}

void checkcycle(){

    vector<int>path(v,0);

  dfs(0,path);

}

Tpoplogical sort uncompleted

 #include<bits/stdc++.h>

using namespace std;

class Graph {

vector<vector<int>>adj;

int v;

public:

void no_node(int n) {

v = n;

adj.resize(n);

}

void addEdge(int i,int j) {

adj[i].push_back(j);

// adj[j].push_back(i);

}

void show() {

for(int i=0; i<v; i++) {

for(int j=0; j<adj[i].size(); j++) {

cout<<adj[i][j]<<" ";

}

cout<<endl;

}

}

bool Dc_DFS(int node,vector<vector<int>>&edges,int parent,vector<int>&v){

        if(!v[node])v[node] = 1;

        else return 1;

        for(int i=0;i<edges[node].size();i++){

            if(edges[node][i]==parent) continue;

            if(Dc_DFS(edges[node][i],edges,node,v)){

                return 1;

            }

        }

        return 0;

    }

void Check_Cycle_DFS(){

    vector<int>visited(v,0);

    if(Dc_DFS(0,adj,-2,visited)){

        cout<<"cycle exists";

    }

    cout<<endl;

}

void Check_Cycle_BFS(){

    vector<int>visited(v,0);

    queue<pair<int,int>>q;

    q.push({-1,0});

    visited[0]=1;

    while(!q.empty()){

        auto  x=q.front();

        int item=x.second;

        int p=x.first;

        q.pop();

        for(int i:adj[item]){

            if(i==p) continue;

            if(visited[i]){

                cout<<"there is cycle";

                return;

            }

            else{

                q.push({item,i});

                visited[i]=1;

            }

        }

    }

}

void sorting(int node,stack<int>&st,vector<int>&v,vector<vector<int>>&adj){

    v[node]=1;

    for(int x:adj[node]){

        if(!v[x])sorting(x,st,v,adj);

    }

    st.push(node);

}

void Topological_sort(){

     stack<int>st;

     vector<int>V(v,0);

     sorting(0,st,V,adj);

     while(!st.empty()){

      cout<<st.top()<<" ";

      st.pop();

}

     

     

   

 }

};

int main() {

Graph g;

g.no_node(4);

g.addEdge(0,1);

g.addEdge(0,2);

g.addEdge(1,3);

g.addEdge(2,3);

g.show();

// g.Check_Cycle_DFS();

// g.Check_Cycle_BFS();

    g.Topological_sort();

}

CHEckign cycle usign bfs and dfs methods

 #include<bits/stdc++.h>

using namespace std;

class Graph {

vector<vector<int>>adj;

int v;

public:

void no_node(int n) {

v = n;

adj.resize(n);

}

void addEdge(int i,int j) {

adj[i].push_back(j);

adj[j].push_back(i);

}

void show() {

for(int i=0; i<v; i++) {

for(int j=0; j<adj[i].size(); j++) {

cout<<adj[i][j]<<" ";

}

cout<<endl;

}

}

bool Dc_DFS(int node,vector<vector<int>>&edges,int parent,vector<int>&v){

        if(!v[node])v[node] = 1;

        else return 1;

        for(int i=0;i<edges[node].size();i++){

            if(edges[node][i]==parent) continue;

            if(Dc_DFS(edges[node][i],edges,node,v)){

                return 1;

            }

        }

        return 0;

    }

void Check_Cycle_DFS(){

    vector<int>visited(v,0);

    if(Dc_DFS(0,adj,-2,visited)){

        cout<<"cycle exists";

    }

    cout<<endl;

}

void Check_Cycle_BFS(){

    vector<int>visited(v,0);

    queue<pair<int,int>>q;

    q.push({-1,0});

    visited[0]=1;

    while(!q.empty()){

        auto  x=q.front();

        int item=x.second;

        int p=x.first;

        q.pop();

        for(int i:adj[item]){

            if(i==p) continue;

            if(visited[i]){

                cout<<"there is cycle";

                return;

            }

            else{

                q.push({item,i});

                visited[i]=1;

            }

        }

    }

}

};

int main() {

Graph g;

g.no_node(3);

g.addEdge(0,1);

g.addEdge(1,2);

g.addEdge(2,0);

g.show();

g.Check_Cycle_DFS();

g.Check_Cycle_BFS();

}

Graph representation using Adjacensy List using linked list O(1) insertion time And BFS Traversal and DFS traversal

#include <iostream>

#include<bits/stdc++.h>

using namespace std;

// Linked list node

struct Node {

int data;

Node* next;

Node(int value) {

data=value;

next=NULL;

}

};

// Graph

class Graph {

int V;

Node* adj[10];

public:

Graph(int v) {

V = v;

// initialize all lists empty

for (int i = 0; i < V; i++)

adj[i] = NULL;

}

void addEdge(int u, int v) {

// add v to u

Node* n1 = new Node(v);

n1->next=adj[u];

adj[u] = n1;

// add u to v

Node* n2 = new Node(u);

n2->next=adj[v];

adj[v] = n2;

}

void print() {

for (int i = 0; i < V; i++) {

cout << i << ": ";

Node* temp = adj[i];

while (temp != NULL) {

cout << temp->data << " -> ";

temp = temp->next;

}

cout << "NULL\n";

}

}

void BFS() {

queue<int>q;

unordered_map<int,int>um;

//int x = rand() % V;

int x=0;

q.push(x);

um[x]=1;

while(!q.empty()) {

int temp=q.front();

cout<<temp<<" ";

q.pop();

Node* point=adj[temp];

while(point) {

if(!um[point->data]) {

q.push(point->data);

um[point->data]=1;

}

point=point->next;

}

}

}

void DFS(int node,unordered_map<int,int>&visited) {

cout<<node<<" ";

visited[node]=1;

Node*point=adj[node];

while(point) {

if(!visited[point->data]) {

DFS(point->data,visited);

}

point=point->next;

}

}

};

int main() {

Graph g(7);

/* g.addEdge(0,3);

g.addEdge(0,1);

g.addEdge(0,2);

g.addEdge(1,2);

g.addEdge(2,3);

g.addEdge(2,4);

g.addEdge(2,5);

g.addEdge(3,4);

g.addEdge(4,5);*/

g.addEdge(0,1);

g.addEdge(0,3);

g.addEdge(1,2);

g.addEdge(3,4);

g.addEdge(4,5);

g.addEdge(5,6);

unordered_map<int,int>um;

g.print();

cout<<"***********************"<<endl;

g.BFS();

cout<<endl;

cout<<"*******************"<<endl;

g.DFS(0,um);

}

HEAP

 #include<bits/stdc++.h>

using namespace std;

void Heapify(vector<int>&arr,int value) {

arr.push_back(value);

int i=arr.size()-1;

while(i>0) {

int parent=(i-1)/2;

if(arr[parent]<arr[i]) {

swap(arr[parent],arr[i]);

i=parent;

} else {

break;

}

}

}

int main() {

vector<int>heap;

Heapify(heap,3);

Heapify(heap,4);

Heapify(heap,5);

Heapify(heap,67);

Heapify(heap,1);

for(int x:heap)

cout<<x<<" ";

}