DAY 36 - Bipartite Graph

Hey everyone! Welcome back to another day of problem-solving. It's day 36, and I'm still going strong on my quest for consistency. Today, we have an interesting problem to tackle. But before we dive in, let's make sure we're all on the same page.

Incase you are unfamiliar with graphs I suggest reading the previous article 32 && 33. It also contains the links to valuable resources.

Question : Bipartite Graph

Given an adjacency list of a graph adj of V no. of vertices having 0 based index. Check whether the graph is bipartite or not.
Note: The graph have can have not connected components.

Example 1:

Input:

• Output: 1
• Explanation: The given graph can be colored
• in two colors so, it is a bipartite graph.

Example 2:

• 
• Output: 0
• Explanation: The given graph cannot be colored
• in two colors such that color of adjacent
• vertices differs.

Intuition:

• We will use a simple bfs/dfs approach keeping count of all colors.
• We will use a color convention of 0 and 1.
• We will start by keeping the first color 0 and then so on changing the color of node based on its adjacenecy list

• Classic stuff like done in previous articles.

  Algorithm:

• Create a function dfs that takes the current node, its color, the adjacency list, and a vector to store the colors of the nodes.

• Set the color of the current node to the provided color.

• Iterate through the adjacency list of the current node:

• If the color of the adjacent node is -1 (indicating it has not been visited), recursively call dfs on the adjacent node, passing the opposite color.

• If the color of the adjacent node is the same as the current node's color, return false, as this violates bipartiteness.

• If all adjacent nodes have been processed and no violations were found, return true.

• Create a function isBipartite that takes the number of vertices, the adjacency list, and returns a boolean.

• Create a vector color of size V to store the colors of the nodes, initialized with -1 (indicating unvisited).

• Iterate through all vertices:

• If the color of the current vertex is -1, call dfs on the current vertex with color 0.

• If the dfs function returns false, indicating a violation of bipartiteness, return false.

• If all vertices have been processed without any violations, return true.

Code:

bool dfs(int node, int col, vector<int> adj[], vector<int>& color) {
    color[node] = col;

    for (auto it : adj[node]) {
        if (color[it] == -1) {
            if (!dfs(it, !col, adj, color)) {
                return false;
            }
        } else if (color[it] == col) {
            return false;
        }
    }

    return true;
}

bool isBipartite(int V, vector<int> adj[]) {
    vector<int> color(V, -1);

    for (int i = 0; i < V; i++) {
        if (color[i] == -1) {
            if (!dfs(i, 0, adj, color)) {
                return false;
            }
        }
    }

    return true;
}

Complexity Analysis:

• Time Complexity:O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because we visit each vertex and its adjacent vertices once.
• Space Complexity:O(V) since we use a vector to store the colors of the nodes.