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