Is Graph Bipartite?

Problem Statement

In the given problem, we are provided with an undirected graph formed by n nodes, identifiable by indices from 0 to n-1. This graph is represented using a 2D array graph, where graph[u] enumerates all nodes directly connected to node u. Key characteristics of this graph include:

• No node links to itself (graph[u] excludes u), which rules out any self-edges.
• Each connection between nodes is unique, ensuring no repetitive or parallel edges.
• The graph's nature is undirected; implying an edge from u to v mandates a reciprocal edge from v to u.
• It's possible for the graph to be disjoint, wherein certain node pairs remain unconnected.

The primary objective is to determine if this graph can be classified as bipartite. A graph is termed bipartite if its nodes can be divided into two distinct groups such that every edge bridges one node from each group. The resolution should be boolean true if the graph is bipartite and false otherwise.

Examples

Example 1

Input:

graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output:

false

Explanation:

There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2

Input:

graph = [[1,3],[0,2],[1,3],[0,2]]

Output:

true

Explanation:

We can partition the nodes into two sets: {0, 2} and {1, 3}.

Constraints

• graph.length == n
• 1 <= n <= 100
• 0 <= graph[u].length < n
• 0 <= graph[u][i] <= n - 1
• graph[u] does not contain u.
• All the values of graph[u] are unique.
• If graph[u] contains v, then graph[v] contains u.

Approach and Intuition

The classification of a graph as bipartite rests on whether it can be colored using two colors without two adjacent nodes sharing the same color. To understand the solution, consider the following steps based on the provided examples:

1. Initiate a coloring attempt by selecting an initial node and assigning it a color (say, color 1).
2. Use BFS (Breadth First Search) or DFS (Depth First Search) to attempt coloring the graph. During this traversal:
   • Color an unvisited adjacent node with the opposite color.
   • If a node is already colored with the wrong color (same color as current node), then the coloring is invalid, and the graph isn't bipartite.

For Example 1:

• Given the adjacency list [[1,2,3],[0,2],[0,1,3],[0,2]]:
  • Starting from node 0 and coloring it, leads to an attempt to color nodes 1, 2, 3 differently but fails as node 2 would require two different colors simultaneously, based on its adjacency with both 0 and 1.
• The process early exits with a bipartite classification as false.

For Example 2:

• With the graph [[1,3],[0,2],[1,3],[0,2]]:
  • A valid bipartite coloring can be established (0 and 2 with one color, 1 and 3 with the other), fulfilling the criteria for all connecting edges.
• The approach confirms the graph is bipartite with a return value of true.

Enhancing this basic understanding with further checks like disconnected components and ensuring all component-specific colorings align with bipartite requirements will frame the complete solution.

Solutions

class Solution {
public:
    bool canPartition(vector<vector<int>>& adjacencyList) {
        int vertexCount = adjacencyList.size();
        vector<int> colors(vertexCount, -1);

        for (int vertex = 0; vertex < vertexCount; ++vertex) {
            if (colors[vertex] == -1) {
                stack<int> nodes;
                nodes.push(vertex);
                colors[vertex] = 0;

                while (!nodes.empty()) {
                    int current = nodes.top();
                    nodes.pop();

                    for (int neighbor : adjacencyList[current]) {
                        if (colors[neighbor] == -1) {
                            nodes.push(neighbor);
                            colors[neighbor] = colors[current] ^ 1;
                        } else if (colors[neighbor] == colors[current]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};

class Solution {
    public boolean checkBipartite(int[][] adjacencyList) {
        int vertices = adjacencyList.length;
        int[] colors = new int[vertices];
        Arrays.fill(colors, -1);

        for (int i = 0; i < vertices; ++i) {
            if (colors[i] == -1) {
                Stack<Integer> dfsStack = new Stack();
                dfsStack.push(i);
                colors[i] = 0;

                while (!dfsStack.empty()) {
                    Integer current = dfsStack.pop();
                    for (int neighbor: adjacencyList[current]) {
                        if (colors[neighbor] == -1) {
                            dfsStack.push(neighbor);
                            colors[neighbor] = colors[current] ^ 1;
                        } else if (colors[neighbor] == colors[current]) {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }
}