Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Divyanshu Varma
Incorrect DSU solution C++

Divyanshu Varma

Apr 19, 2025

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 you process all edges without finding a conflict (find(u) == find(v)), the graph is bipartite. Return true.

1

0

Comments
Comments
Divyanshu Varma
Divyanshu Varma6 months ago
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, 0); // {0 uncolored, 1&2 colored}
        for(int i = 0; i < n; i++) {
            if(color[i] == 0) {
                if...

On this page