leetcode bi-partition 886.cpp

class Solution {
    bool isbipartite(vector<vector<int>>&adj, int N, int node,vector<int>&color)
    {
        queue<int>q;
        q.push(node);
        color[node]=1;
        while(!q.empty())
        {
            int curr=q.front();
            q.pop();
            for(auto x:adj[curr])
            {
                if(color[x]==color[curr])
                {
                    return false;
                }
                if(color[x]==-1)
                {
                    color[x]=1-color[curr];
                    q.push(x);
                }
            }
        }
        return true;
    }
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        vector<vector<int>>adj(N+1);
        for(int i=0;i<dislikes.size();i++)
        {
            adj[dislikes[i][0]].push_back(dislikes[i][1]);
            adj[dislikes[i][1]].push_back(dislikes[i][0]);
        }
        
        vector<int>color(N+1, -1);
        for(int i=1;i<=N;i++)
        {
            if(color[i]==-1)
            {
                if(!isbipartite(adj, N, i, color))
                {
                    return false;
                }
            }
        }
        return true;
        
    }
};

leetcode clone graph 133 .cpp

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

class Solution {
    void dfs(Node* curr,Node* node,vector<Node *>& visited)
    {
        //Node* copy = new Node(node->val);
        visited[node->val] = node;
        for(auto ele: curr->neighbors)
        {
            if(visited[ele->val] == NULL)
            {
                Node *newnode = new Node(ele->val);
                (node->neighbors).push_back(newnode);
                dfs(ele,newnode,visited);
            }
            else
                (node->neighbors).push_back(visited[ele->val]);
        }
    }
public:
    Node* cloneGraph(Node* node) {
        if(node==NULL)
            return NULL;
        
        vector<Node *> visited(1000,NULL);
        Node* copy = new Node(node->val);
        visited[node->val] = copy;
        //Iterate for all neighbors
        for(auto curr: node->neighbors)
        {
            if(visited[curr->val] == NULL)
            {
                Node *newnode = new Node(curr->val);
                (copy->neighbors).push_back(newnode);
                dfs(curr,newnode,visited);
            }
            else
                (copy->neighbors).push_back(visited[curr->val]);
        }
        return copy;
    }
};


static int fastio = []() {
    //#define endl '\n'
    std::ios::sync_with_stdio(false);
    //std::cin.tie(NULL);
    //std::cout.tie(0);
    return 0;
}();

leetcode course schedule 207.cpp

class Solution {
    bool isCyclic(vector<vector<int>>& adj,vector<int>& visited,int curr)
    {
        if(visited[curr]==2)
            return true;
        
        visited[curr] = 2;
        for(int i=0;i<adj[curr].size();++i)
            if(visited[adj[curr][i]]!=1)
                if(isCyclic(adj,visited,adj[curr][i]))
                    return true;
        
        visited[curr] = 1;
        return false;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        
        vector<vector<int>> adj(numCourses);
        //Make adjacency matrix (Directed graph)
        for(int i=0;i<prerequisites.size();++i)
            adj[prerequisites[i][0]].push_back(prerequisites[i][1]);
        
        vector<int> visited(numCourses,0);
        for(int i=0;i<numCourses;++i)
            if(visited[i]==0)
                if(isCyclic(adj,visited,i))
                    return false;
        
        return true;
    }
};

leetcode island 200 dfs .cpp

class Solution {
    void mark_curr_island(vector<vector<char>>&grid, int x, int y, int r, int c)
    {
        
        if(x<0||y<0||x>=r||y>=c||grid[x][y]!='1')
            return ;
        
        grid[x][y]='2';
        mark_curr_island(grid, x, y+1, r, c);
        mark_curr_island(grid, x+1, y, r, c);
        mark_curr_island(grid, x-1, y, r, c);
        mark_curr_island(grid, x, y-1, r, c);
        
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int r=grid.size();
        if(r==0)
            return 0;
        int c=grid[0].size();
        
        int cnt=0;
        
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(grid[i][j]=='1')
                {
                    mark_curr_island(grid, i, j, r, c);
                    cnt++;
                }
            }
           
        }
         return cnt;
    }
    
};