Блог пользователя rohit_thapliyal2000

Автор rohit_thapliyal2000, история, 12 дней назад, По-английски,

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 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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