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;
}
