Grokking Graph Algorithms for Coding Interviews

0% completed

​

Solution: Is Graph Bipartite?

Problem Statement

Given a 2D array graph[][], representing the undirected graph, where graph[u] is an array of nodes that are connected with node u.

Determine whether a given undirected graph is a bipartite graph.

The graph is a bipartite graph, if we can split the set of nodes into two distinct subsets such that no two nodes within the same subset are adjacent (i.e., no edge exists between any two nodes within a single subset).

Examples

  1. Example 1:
    • Input: graph = [[1,3], [0,2], [1,3], [0,2]]
  • Expected Output: true

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lee

· 2 years ago

The solutions explanation would lead you to believe that you need only check if the two nodes connected by the edge belong to the same subset. If they do, the graph is not bipartite.

This is not correct though, as the code that matches this description fails. Then, looking at the solution code in python, you see some tricky stuff is happening with the first neighbor in the set of neighbors for each node. This is not explained at all in the solution. It's not clear how or why this code succeeds at detecting whether or not the graph is bipartite.

Show 3 replies
Divyanshu Varma

Divyanshu Varma

· a year ago

The given DSU solution for C++ is incorrect! I am writing the correct logic below but it's just better to use BFS/DFS for this 2-coloring/bipartiteness problem.

You can use DSU, but it needs modification. A common way is to use 2n elements in the DSU. For each node i (0 to n-1), you have two representatives: i (meaning i is in set A) and i + n (meaning i is in set B).

For each edge (u, v) in the input:

Check if u and v are already connected in the DSU (find(u) == find(v)). If yes, it means the graph forces u and v into the same partition, but they have an edge between them. The graph is not bipartite. Return false.

Perform unions to link the opposing partitions: unite(u, v + n) and unite(u + n, v). This signifies "if u is in A, v must be in B" and "if u is in B, v must be in A".

If yo

Show 1 reply