rohit_thapliyal2000's blog

By rohit_thapliyal2000, history, 12 days ago, In English,

I used Disjoint sets for the 0-difference edges and check for bipartite graph for 1-difference edges. The array zero is for 0-difference disjoint set, array hero holds the parent of every element, array arank defines the rank of every set (used for union-by-rank) and the array whatup checks if all the same set element(0-difference elements) have the same color(have no difference at all).

Here is the code : CODE

 
 
 
 

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rohit_thapliyal2000 (previous revision, new revision, compare).

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Use Bipartite graph matching theory. Adjacent nodes will be of same color if the difference is zero, or of different color if the difference is one. If you can bi-color the graph, answer is YES, otherwise NO