HackerRank Black and White Tree problem solution

In this HackerRank Black and White Tree problem solution we have given the decomposed graph, construct and shade a valid connected graph such that the difference |nw – nb| between its shaded nodes is minimal.

Problem solution in Java.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
public class BlackAndWhiteTree {
    static final List<Graph> graphs = new ArrayList<>();
    static int ones = 0;
    static int zeroes = 0;
    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] line = br.readLine().split(" ");
            Node[] nodes = new Node[Integer.parseInt(line[0])];
            for (int e = 0; e < nodes.length; e++) {
                nodes[e] = new Node(e);
            }
            for (int e = Integer.parseInt(line[1]); e > 0; e--) {
                line = br.readLine().split(" ");
                nodes[Integer.parseInt(line[0]) - 1].adjacent.add(nodes[Integer.parseInt(line[1]) - 1]);
                nodes[Integer.parseInt(line[1]) - 1].adjacent.add(nodes[Integer.parseInt(line[0]) - 1]);
            }
            int components = 0;
            for (int e = 0; e < nodes.length; e++)
                if (!nodes[e].visited) {
                    Graph g = new Graph(nodes[e]);
                    if (g.diffs == 0) {
                        zeroes++;
                    } else if (g.diffs == 1) {
                        ones++;
                    } else {
                        components += g.diffs;
                    }
                    graphs.add(g);
                }
            Collections.sort(graphs, (g1, g2) -> Math.abs(g1.diffs) - Math.abs(g2.diffs));
            final int SIZE = components / 2 + 1;
            boolean[] dinam = new boolean[SIZE];
            int[] parent = new int[SIZE];
            Arrays.fill(parent, Integer.MAX_VALUE);
            dinam[0] = true;
            int lastMax = 0;
            for (int g = ones + zeroes; g < graphs.size(); g++) {
                final int dif = graphs.get(g).diffs, top = Math.min(SIZE, lastMax + dif + 1);
                for (int e = top - 1; e >= dif; e--) {
                    dinam[e] |= dinam[e - dif];
                    if (dinam[e - dif]) {
                        parent[e] = Math.min(parent[e], dif);
                    }
                }
                lastMax += dif;
            }
            int min = 0;
            int mindiff = components;
            for (int e = 0; e < SIZE; e++)
                if (dinam[e] && calcMin(Math.abs(components - 2 * e)) < calcMin(Math.abs(components - 2 * min))) {
                    min = e;
                    mindiff = Math.abs(components - 2 * e);
                }
            final int minValue = calcMin(Math.abs(components - 2 * min));
            for (int g = graphs.size() - 1; g >= 0; g--) {
                if (graphs.get(g).diffs == 0) {
                } else if (graphs.get(g).diffs == 1) {
                    graphs.get(g).signum = g < zeroes + mindiff || (g % 2) == 1;
                } else if (min > 0 && parent[min] == graphs.get(g).diffs) {
                    graphs.get(g).signum = true;
                    min -= graphs.get(g).diffs;
                }
            }
            Collections.sort(graphs, (g1, g2) -> Boolean.compare(g1.signum, g2.signum));
            Graph root = graphs.get(graphs.size() - 1);
            System.out.println(minValue + " " + (graphs.size() - 1));
            for (int g = 0; g < graphs.size() - 1; g++) {
                if (graphs.get(g).signum == root.signum) {
                    root.root.adjacent.get(0).adjacent.add(graphs.get(g).root);
                    graphs.get(g).root.adjacent.add(root.root.adjacent.get(0));
                    System.out.println(root.root.adjacent.get(0).id + " " + graphs.get(g).root.id);
                } else {
                    root.root.adjacent.add(graphs.get(g).root);
                    graphs.get(g).root.adjacent.add(root.root);
     System.out.println(root.root.id + " " + graphs.get(g).root.id);
                }
            }
        }
    }
    public static int calcMin(int x) {
        if (ones < x) {
            return x - ones;
        }
        return (ones - x) % 2;
    }
    static class Graph {
        Node root;
        int whites, blacks, diffs, size;
        boolean signum = false;
        public Graph(Node root) {
            this.root = root;
            Stack<Node> n = new Stack<>();
            n.add(root);
            while (!n.isEmpty()) {
                Node next = n.pop();
                if (next.visited)
                    continue;
                next.parent = root.parent;
                next.visited = true;
                if (next.isWhite) {
                    whites++;
                } else {
                    blacks++;
                }
                for (Node e : next.adjacent) {
                    e.isWhite = !next.isWhite;
                    n.push(e);
                }
            }
            diffs = blacks - whites;
            size = blacks + whites;
            if (blacks - whites < 0) {
                invert();
            }
        }
        public void invert() {
            root = root.adjacent.get(0);
            int t = blacks;
            blacks = whites;
            whites = t;
            diffs = blacks - whites;
            size = blacks + whites;
        }
    }
    static class Node {
        int parent, id;
        boolean isWhite, visited;
        ArrayList<Node> adjacent = new ArrayList<>();
        public Node(int parent) {
            this.parent = parent;
            this.id = parent + 1;
        }
    }
}

Problem solution in C++.

#include <bits/stdc++.h>
using namespace std;

#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair

#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

#define pr1(x) printf("%dn",x)
#define pr2(x,y) printf("%d %dn",x,y)
#define pr3(x,y,z) printf("%d %d %dn",x,y,z)

#define prll1(x) printf("%lldn",x)
#define prll2(x,y) printf("%lld %lldn",x,y)
#define prll3(x,y,z) printf("%lld %lld %lldn",x,y,z)

#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int N=200010;
int w[2];
vector <int> v[N];
int a[N], d[N], p[N], c[N], col[N], sz, ccol[2][N];
bool f[N];
queue<int> q[N];
void dfs(int x,int y)
{
    f[x]=1;
    w[y]++;
    col[x] = y;
    ccol[y][sz] = x;
    for (int i=0;i<v[x].size();i++)
    if (!f[v[x][i]])
        dfs(v[x][i],(y^1));
    else if( col[v[x][i]] != 1 - y ) 
        assert(0);
}

int main() 
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=0,x,y;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    int k=0;
    for (int i=1;i<=n;i++) 
    {
        if (!f[i]) 
        {
            w[0] = w[1]=0;
            dfs(i,0);
            c[i] = (w[0] < w[1]);
            k+=abs(w[0]-w[1]);
            a[abs(w[0]-w[1])]++;
            q[abs(w[0]-w[1])].push( i );
        }
    }

    for (int j=1;j<=k;j++) 
        d[j]=N;

    for (int i=1;i<=n;i++)
    {
        if (a[i]) 
        {
            for (int j=0;j+i<=k;j++) 
            {
                if( d[i+j] == N && d[j] != N ) 
                {
                    d[i+j] = d[j] + 1;
                    p[i+j] = j;
                }
            }

            for (int j=1;j<=k;j++) 
            {
                if (d[j]>a[i]) 
                {
                    d[j]=N;
                    p[j]=0;
                } 
                else 
                {
                    d[j]=0;
                }
            }
        }
    }
    
    int ans=k, v = 0;
    for (int i=0;i<=k;i++) 
    {
        if(d[i]<N) 
        {
            if( ans >= abs(k - 2 * i) ) 
            {
                ans = abs(k - 2 * i);
                v = i;
            }
        }
    }

    memset(f, 0, sizeof f);
    while( v != 0 ) 
    {
        int diff = v - p[v];
        int nd = q[diff].front();
        q[diff].pop();
        sz ++;
        dfs(nd, c[nd]);
        v = p[v];
    }

    for(int i=1; i<=n; i++) 
    {
        if( !f[i] ) 
        {
            sz ++;
            dfs(i, 1 - c[i]);
        }
    }

    int blk, wht, idb, idw;
    blk = wht = idb = idw = -1;
    for(int i=1; i<=sz; i++) 
    {
        if( ccol[0][i] ) 
        {
            blk = ccol[0][i];
            idb = i;
        }

        if( ccol[1][i] ) 
        {
            wht = ccol[1][i];
            idw = i;
        }
    }
    cout << ans << " " << sz - 1 << "n";
    if( idb != idw ) cout << blk << " " << wht << "n";
    for(int i=1; i<=sz; i++) 
    {
        if( i != idb && i != idw ) 
        {
            if( ccol[0][i] ) 
            {
                cout << wht << " " << ccol[0][i] << "n";
            } 
            else 
            {
                cout << blk << " " << ccol[1][i] << "n";
            }
        }
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 1234555
typedef struct _node{
  int t;
  int i;
  int c;
  int a;
  struct _node *next;
} node;
typedef struct _lnode{
  int x;
  int w;
  struct _lnode *next;
} lnode;
int abss(int x);
void insert_edge(int x,int y,int w);
void dfs(int x,int c);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
void sort_a_ad(int*a,int*c,int size,int*new_size);
void merge_ad(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size);
void insert(int target,int idx,int c,int a);
int search(int target,int idx,int *c);
int solve(int target,int target2,int idx);
void clean_table();
int N,w,b,ngs,*cans,*cdiff,*c,idx[200000],*trace,mark[200000]={0},diff[200000],f[200000],s[200000],*remain;
lnode **table;
node *hash[HASH_SIZE]={0};

int main(){
  int M,x,y,gs,sum,ans,target,i,j,k;
  scanf("%d%d",&N,&M);
  table=(lnode**)malloc(N*sizeof(lnode*));
  memset(table,0,N*sizeof(lnode*));
  for(i=0;i<M;i++){
    scanf("%d%d",&x,&y);
    insert_edge(x-1,y-1,1);
  }
  trace=(int*)malloc(N*sizeof(int));
  memset(trace,0,N*sizeof(int));
  for(i=gs=0;i<N;i++)
    if(!trace[i]){
      w=b=0;
      dfs(i,0);
      x=i;
      if(table[i])
        y=table[i]->x;
      else
        y=-1;
      if(w>b){
        diff[gs]=w-b;
        f[gs]=x;
        s[gs]=y;
      }
      else{
        diff[gs]=b-w;
        f[gs]=y;
        s[gs]=x;
      }
      idx[gs]=gs;
      gs++;
    }
  free(trace);
  clean_table();
  free(table);
  cdiff=(int*)malloc(gs*sizeof(int));
  c=(int*)malloc(gs*sizeof(int));
  for(i=sum=0,ans=200001;i<gs;i++){
    sum+=diff[i];
    cdiff[i]=diff[i];
    c[i]=1;
  }
  target=sum/2;
  sort_a2(diff,idx,gs);
  sort_a_ad(cdiff,c,gs,&ngs);
  remain=(int*)malloc(ngs*sizeof(int));
  if(!M || ngs==1){
    printf("%d %dn",gs%2*cdiff[0],gs-1);
    for(i=0;i<gs-1;i++)
      printf("%d %dn",f[i]+1,f[i+1]+1);
    return 0;
  }
  for(i=0;i<ngs;i++)
    if(i==0)
      remain[i]=c[i]*cdiff[i];
    else
      remain[i]=remain[i-1]+c[i]*cdiff[i];
  ans=solve(target,(sum+1)/2,ngs-1);
  cans=remain;
  memset(cans,0,ngs*sizeof(int));
  for(i=ngs-1;i>=0;i--){
    if(target<=0)
      break;
    if(i==0){
      cans[i]=(target-1)/cdiff[i]+1;
      break;
    }
    search(target,i,&cans[i]);
    if(cans[i]==-1){
      for(j=i;j>=0;j--)
        cans[j]=c[j];
      break;
    }
    target-=cans[i]*cdiff[i];
  }
  for(j=0,k=0;j<gs && k<ngs;k++){
    x=j+cans[k];
    for(;j<x;j++)
      mark[j]=1;
    while(diff[j]==cdiff[k] && j<gs)
      j++;
  }
  printf("%d %dn",abss(2*ans-sum),gs-1);
  for(i=0;i<gs;i++)
    if(s[idx[i]]!=-1)
      k=i;
  for(i=0;i<gs;i++){
    if(i==k)
      continue;
    if(mark[i]!=mark[k])
      printf("%d %dn",f[idx[i]]+1,f[idx[k]]+1);
    else
      printf("%d %dn",f[idx[i]]+1,s[idx[k]]+1);
  }
  return 0;
}
int abss(int x){
  return (x<0)?-x:x;
}
void insert_edge(int x,int y,int w){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->w=w;
  t->next=table[y];
  table[y]=t;
  return;
}
void dfs(int x,int c){
  lnode *p;
  trace[x]=1;
  if(c)
    b++;
  else
    w++;
  for(p=table[x];p;p=p->next)
    if(!trace[p->x])
      dfs(p->x,c^1);
  return;
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}
void sort_a_ad(int*a,int*c,int size,int*new_size){
  if (size < 2){
    (*new_size)=size;
    return;
  }
  int m = (size+1)/2,i;
  int *left_a,*right_a,*left_c,*right_c;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_c=(int*)malloc(m*sizeof(int));
  right_c=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_c[i]=c[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_c[i]=c[i+m];
  }
  int new_l_size=0,new_r_size=0;
  sort_a_ad(left_a,left_c,m,&new_l_size);
  sort_a_ad(right_a,right_c,size-m,&new_r_size);
  merge_ad(a,left_a,right_a,c,left_c,right_c,new_l_size,new_r_size,new_size);
  free(left_a);
  free(right_a);
  free(left_c);
  free(right_c);
  return;
}
void merge_ad(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size){
  int i = 0, j = 0,index=0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      c[index] = right_c[j];
      a[index++] = right_a[j];
      j++;
    } else if (j == right_size) {
      c[index] = left_c[i];
      a[index++] = left_a[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      c[index] = left_c[i];
      a[index++] = left_a[i];
      i++;
    } else {
      c[index] = right_c[j];
      a[index++] = right_a[j];
      j++;
    }
    if(index>1&&a[index-2]==a[index-1]){
      c[index-2]+=c[index-1];
      index--;
    }
  }
  (*new_size)=index;
  return;
}
void insert(int target,int idx,int c,int a){
  int bucket=(target*200000LL+idx)%HASH_SIZE;
  node *t;
  t=(node*)malloc(sizeof(node));
  t->t=target;
  t->i=idx;
  t->c=c;
  t->a=a;
  t->next=hash[bucket];
  hash[bucket]=t;
  return;
}
int search(int target,int idx,int *c){
  int bucket=(target*200000LL+idx)%HASH_SIZE;
  node *t=hash[bucket];
  while(t){
    if(t->t==target && t->i==idx){
      *c=t->c;
      return t->a;
    }
    t=t->next;
  }
  return -1;
}
int solve(int target,int target2,int idx){
  if(target<=0)
    return 0;
  if(target>remain[idx])
    return -1;
  if(target==remain[idx]){
    insert(target,idx,-1,target);
    return target;
  }
  int t,ans=200000,ansc,i;
  if(idx==0){
    t=(target-1)/cdiff[idx]+1;
    return t*cdiff[idx];
  }
  t=search(target,idx,&w);
  if(t!=-1)
    return t;
  for(i=0;i<=c[idx];i++){
    t=solve(target-i*cdiff[idx],target2-i*cdiff[idx],idx-1);
    if(t!=-1){
      if(t+i*cdiff[idx]<ans){
        ans=t+i*cdiff[idx];
        ansc=i;
      }
      if(t+i*cdiff[idx]==target || t+i*cdiff[idx]==target2){
        insert(target,idx,i,t+i*cdiff[idx]);
        return t+i*cdiff[idx];
      }
    }
    if(target-i*cdiff[idx]<=0)
      break;
  }
  insert(target,idx,ansc,ans);
  return ans;
}
void clean_table(){
  int i;
  lnode *p,*pp;
  for(i=0;i<N;i++)
    if(table[i]){
      p=table[i];
      while(p){
        pp=p->next;
        free(p);
        p=pp;
      }
      table[i]=NULL;
    }
  return;
}