Day 42 | Graph Practice [LeetCode] | C++

Today we will be practicing Leetcode problems from what we have learned so far.

So let's get started with solving a few problems

Number of Provinces [Medium]

Solution

This is a straightforward problem of finding the count of connected components

Blog Link

Solution Implementation

class Solution {
public:
    void dfs(int u, vector<int> &vis, vector<vector<int>> &isConnected){
        int n = vis.size();
        vis[u] = 1;
        for(int i = 0; i < n; i++){
            if(vis[i])continue;
            if(isConnected[u][i]){
                dfs(i, vis, isConnected);
            }
        }
    }
    
    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<int> vis(isConnected.size());
        int ans = 0;
        for(int i = 0; i < vis.size(); i++){
            if(vis[i])continue;
            ans++;
            dfs(i,vis,isConnected);
        }
        return ans;
    }
};

Is Graph Bipartite [Medium]

Solution

This is a straightforward problem of checking if a graph is bipartite or not. Blog Link

Solution Implementation

class Solution {
public:
    bool isBipartite(int u, int col, vector<vector<int>> &graph, vector<int> &color){
        color[u] = col;
        for(int i : graph[u]){
            int next_color = col ^ 1;
            if(color[i] != -1){
                if(color[i] != next_color){
                    return false;
                }
                continue;
            }
            if(!isBipartite(i, next_color, graph, color)){
                return false;
            }
        }
        return true;
    }
    bool isBipartite(vector<vector<int>>& graph) {
        vector<int> color(graph.size(),-1);
        for(int i = 0; i < color.size(); i++){
            if(color[i] != -1)continue;
            if(!isBipartite(i, 0, graph, color)){
                return false;
            }
        }
        return true;
    }
};

Keys and Rooms [Medium]

Solution

This is just DFS because rooms are vertices and keys are directed edges. Blog Link

Solution Implementation

class Solution {
public:
    
    void dfs(int u, vector<vector<int>>&g, vector<int> &vis){
        vis[u] = 1;
        for(int i: g[u]){
            if(vis[i])continue;
            dfs(i,g,vis);
        }
    }
    
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<int> vis(rooms.size(),0);
        dfs(0,rooms,vis);
        int all_visited = accumulate(vis.begin(), vis.end(), 0);
        if(all_visited == rooms.size()){
            return true;
        }
        return false;
    }
};

Possible Bipartition [Medium]

Solution

Consider dislikes as edges, then you are just 2-coloring or bipartition the graph then this is just a straightforward problem of checking if a graph is bipartite or not. Blog Link

Solution Implementation

class Solution {
public:
    bool isBipartite(int u, int col, vector<vector<int>> &graph, vector<int> &color){
        color[u] = col;
        for(int i : graph[u]){
            int next_color = col ^ 1;
            if(color[i] != -1){
                if(color[i] != next_color){
                    return false;
                }
                continue;
            }
            if(!isBipartite(i, next_color, graph, color)){
                return false;
            }
        }
        return true;
    }
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<int> color(n+1,-1);
        vector<vector<int>> g(n+1);
        for(auto& i: dislikes){
            g[i[0]].push_back(i[1]);
            g[i[1]].push_back(i[0]);
        }
        for(int i = 1; i <= n; i++){
            if(color[i] != -1) 
                continue;
            if(!isBipartite(i, 0, g, color)){
                return false;
            }
        }
        return true;
    }
};

Flower Planting With No Adjacent [Medium]

Solution

This is just a DFS. Since we know that there are at most 3 adjacent nodes, so at least 1 color will always be available for the current node.

Solution Implementation

class Solution {
public:
    void color_graph(int u, vector<vector<int>> &graph, vector<int> &color){
        set<int> color_options;
        for(int i = 1; i <= 4; i++)
            color_options.insert(i);
        for(int adj: graph[u]){
            if(color[adj] != -1){
                color_options.erase(color[adj]);
            }
        }
        color[u] = *color_options.begin();
        for(int i : graph[u]){
            if(color[i] != -1){
                continue;
            }
            color_graph(i, graph, color);
        }
    }
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<int> color(n+1,-1);
        vector<vector<int>> g(n+1);
        for(auto& i: paths){
            g[i[0]].push_back(i[1]);
            g[i[1]].push_back(i[0]);
        }
        for(int i = 1; i <= n; i++){
            if(color[i] != -1) 
                continue;
            color_graph(i, g, color);
        }
        color.erase(color.begin());
        return color;
    }
};

Please like and share my posts if they are helpful.