Can anyone help me how to check whether a graph is bipartite or not using Disjoint Set Union! Please explain or provide the code using arrays for implementing DSU!
you can use simply dfs to check bipartness
If you want to check whether a graph is bipartite online, read this : bipartiteness online
If you want to check it offline (i.e you already have the entire graph with you before you begin checking), you can simply run dfs from a node and assign parity to each new node visited. If the parent’s parity is 1, then all its children must be assigned 0. Now if you encounter a visited node having the same parity as its parent, the graph isn’t bipartite.
Hope this helps.
1 Like
I saw that website but couldn’t much make out of it. A simple explanation with using dsu would have been useful!
Yaa… but dsu would have lesser time complexity!
Here is the concept using DSU. Do read it completely because some things will become clear on the way. Still if something is not clear let me know …
To check whether graph is bipartite or not first consider the fact that if your graph has odd cycle it is not bipartite because you can never find a partition of set in two such that no two in same set have an edge b/w them. Consider an example of cycle of size 3 or 5 and you will understand why is it so.
So problem reduces to finding whether addition of an edge gives an odd cycle or not. For this you can use parity length concept as suggested by @ade9.
Initially you give same parity to all nodes say 0 then whenever you merge two components change the parity of representative of smaller size set if parity of both representative is same. Why? i will tell you later …
Now as we go on merging nodes we will have a single representative (will always contain parity 0) and remaining nodes which are in that set will have some parity.
Now from each node in the set if you take xor up to the representative it will give you the parity length
This parity length will denote the color of node. So if you want to draw an edge b/w two nodes in same set and color of nodes are same that means this edge will create an odd cycle thereby losing bipartiteness.
Why odd cycle? …Just try to figure it out with pen & paper and get back to me if it doesn’t help.
In case nodes are not in same set we will connect their representative by an edge.
Now i answer that question of changing parity of smaller set while merging two representative of the set if parity is same . This was because when a new edge is added definitely color (parity length) of all nodes in smaller set is going to change because an edge will change cycle length from odd to even and vice versa so if we change parity of representative of smaller set all the nodes beneath it will have their color change because we take xor till the root (i.e. larger set representative) to find the color of any node and that’s what we want to because of addition of a new edge parity length or color should change for all nodes in smaller set.
You can get the code as mentioned in the link by @ade9. Check the parity length concept there too. It will become more clear.
If you find something messy or confusing …do let me know. I will try to resolve it 
Also sorry i am not good at formatting the matter but i have tried to maintain sequence of steps so that it is easy to understand but still you can ping me…
2 Likes