HackerRank Travel in HackerLand problem solution YASH PAL, 31 July 2024 In this HackerRank Travel in HackerLand problem solution, You will be given q queries. Each query takes the form of 3 space-separated integers, x, y, and k, denoting the respective values for starting city, destination city, and a minimum number of unique buildings that David wants to see along the way. For each query, you must print the minimum crowd value for a path between x and y that has at least k different buildings along the route. If there is no such path, print -1. Topics we are covering Toggle Problem solution in Python.Problem solution in Java.Problem solution in C++.Problem solution in C. Problem solution in Python. from collections import defaultdict import heapq def root(ids, i): while ids[i] != i: ids[i] = ids[ids[i]] i = ids[i] return i def union(queries, blds, ids, p, q): i = root(ids, p) j = root(ids, q) if i == j: return i, j if len(blds[i]) > len(blds[j]): bigb, smb = blds[i], blds[j] else: bigb, smb = blds[j], blds[i] for b in smb: bigb.add(b) del smb if len(queries[i][0]) + len(queries[i][1]) > len(queries[j][0]) + len(queries[j][1]): ids[j] = i blds[i] = bigb blds[j] = None return j, i else: ids[i] = j blds[j] = bigb blds[i] = None return i, j n, m, q = map(int, input().split()) T = list(map(int, input().split())) edges = [] for i in range(m): x, y, u = map(int, input().split()) edges.append((u, x-1, y-1)) edges.sort() queries = [[set([]), []] for _ in range(n)] res = [-1 for i in range(q)] for qi in range(q): x, y, k = map(int, input().split()) x, y = sorted([x-1, y-1]) if x == y and k <= 1: res[qi] = 0 else: qr = (k, x, y, qi) if x == y: heapq.heappush(queries[x][1], qr) else: queries[x][0].add(qr) queries[y][0].add(qr) ids = [i for i in range(n)] blds = [set([T[i]]) for i in range(n)] for u, x, y in edges: i, j = union(queries, blds, ids, x, y) if i == j: continue tot_blds = len(blds[j]) #print u, x, y, i, j, queries[i], queries[j], tot_blds for qr in queries[i][0]: if root(ids, qr[1]) != root(ids, qr[2]): queries[j][0].add(qr) else: queries[j][0].discard(qr) if tot_blds >= qr[0]: res[qr[-1]] = u else: heapq.heappush(queries[j][1], qr) while queries[i][1] and queries[i][1][0][0] <= tot_blds: res[queries[i][1][0][-1]] = u heapq.heappop(queries[i][1]) for qr in queries[i][1]: heapq.heappush(queries[j][1], qr) queries[i][0] = None queries[i][1] = None while queries[j][1] and queries[j][1][0][0] <= tot_blds: res[queries[j][1][0][-1]] = u heapq.heappop(queries[j][1]) for r in res: print(r) {“mode”:”full”,”isActive”:false} Problem solution in Java. import java.io.*; import java.util.*; public class Solution { static TreeSet<Integer>[] all; static int ind; static void swapAll(int root_A, int root_B) { TreeSet<Integer> tmp = all[root_A]; all[root_A] = all[root_B]; all[root_B] = tmp; } static class DisjointUnionSets { int[] parent; int[] rank; public DisjointUnionSets(int n) { parent = new int[n]; rank = new int[n]; } int findset(int x) { return x == parent[x] ? x : findset(parent[x]); } void union(int x, int y) { int xRoot = findset(x); int yRoot = findset(y); if (xRoot == yRoot) { return; } if (rank[xRoot] < rank[yRoot]) { parent[xRoot] = parent[yRoot]; rank[yRoot] += rank[xRoot]; if (all[xRoot].size() > all[yRoot].size()) { swapAll(xRoot, yRoot); } while (all[xRoot].size() > 0) { int tmp = all[xRoot].pollFirst(); all[yRoot].add(tmp); } } else { parent[yRoot] = parent[xRoot]; rank[xRoot] += rank[yRoot]; if (all[xRoot].size() < all[yRoot].size()) { swapAll(xRoot, yRoot); } while (all[yRoot].size() > 0) { int tmp = all[yRoot].pollFirst(); all[xRoot].add(tmp); } } } } static class QS { int x, y, k, id; public QS(int x, int y, int k, int id) { this.x = x; this.y = y; this.k = k; this.id = id; } } static class Edge { int u; int v; public Edge(int xx, int yy) { this.u = xx; this.v = yy; } } static class EdgeW { int w; Edge edge; public EdgeW(int xx, Edge yy) { this.w = xx; this.edge = yy; } } static EdgeW[] edges; static void apply(DisjointUnionSets dus, int k) { while (ind < edges.length) { if (edges[ind].w > k) { break; } else { dus.union(edges[ind].edge.u, edges[ind].edge.v); ind++; } } } @SuppressWarnings("unchecked") public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); Map<Integer, Integer> map = new HashMap<>(); int cntb = 0; int[] revmp1 = new int[n + 1]; st = new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) { int item = Integer.parseInt(st.nextToken()); if (!map.containsKey(item)) { map.put(item, ++cntb); } revmp1[i] = map.get(item); } edges = new EdgeW[m]; for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); edges[i] = new EdgeW(w, new Edge(u, v)); } Arrays.sort(edges, (a, b) -> a.w - b.w); int[] revmp2 = new int[m+1]; int cnte = 0; map.clear(); for (int k = 0; k < edges.length; k++) { EdgeW i = edges[k]; if (!map.containsKey(i.w)) { map.put(i.w, ++cnte); revmp2[cnte] = i.w; } edges[k].w = map.get(i.w); } int tot = 0; int[] ans = new int[q]; QS[] qs = new QS[q+1]; for (int i = 0; i < q; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); if (w > cntb) { ans[i] = -1; } else { tot++; qs[tot] = new QS(u, v, w, i); } } int[] lo = new int[tot + 1]; int[] hi = new int[tot + 1]; for (int i = 1; i <= tot; i++) { lo[i] = 1; hi[i] = cnte + 1; } Stack<Integer>[] check = new Stack[Math.max(n + 1, m)]; all = new TreeSet[n + 1]; for (int i = 0; i <= n; i++) { all[i] = new TreeSet<>(); } for (int i = 0; i < check.length; i++) { check[i] = new Stack<>(); } DisjointUnionSets dus = new DisjointUnionSets(n + 1); boolean changed = true; while (changed) { changed = false; for (int i = 0; i <= n; i++) { all[i].clear(); all[i].add(revmp1[i]); dus.parent[i] = i; dus.rank[i] = 1; } int upto = 0; for (int i = 1; i <= tot; i++) { if (lo[i] != hi[i]) { check[(lo[i] + hi[i]) >> 1].add(i); upto = Math.max(upto, (lo[i] + hi[i]) >> 1); } } ind = 0; for (int i = 1; i <= upto; i++) { apply(dus, i); while (check[i].size() > 0) { changed = true; int id = check[i].pop(); int rootx = dus.findset(qs[id].x); int rooty = dus.findset(qs[id].y); if (rootx != rooty) { lo[id] = i + 1; } else { if (all[rootx].size() >= qs[id].k) { hi[id] = i; } else { lo[id] = i + 1; } } } } } for (int i = 1; i <= tot; i++) { if (lo[i] <= cnte) { ans[qs[i].id] = revmp2[lo[i]]; } else { ans[qs[i].id] = -1; } } for (int i = 0; i < q; i++) { bw.write(ans[i] + "n"); } bw.newLine(); bw.close(); br.close(); } } {“mode”:”full”,”isActive”:false} Problem solution in C++. #include <set> #include <cmath> #include <queue> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define sz2 200001 #define ii pair<int, int> #define pb push_back #define mp make_pair #define ff first #define ss second int qq, N, M, Q, K, C, max_edge = 1000000001; vector<ii > G[100001]; vector<pair<int, ii > > E; priority_queue<pair<int, ii > > pq; pair <int, ii > q[2000001]; int lvl[sz2],T[100001],a[1000001],L[sz2], R[sz2],p[sz2],parent[sz2][20],col[100001], ll[sz2],rr[sz2],weight[sz2],dis[sz2], ans[2000001],st[5000005],used[10000001]; bool vis[100001]; int mycmp(pair <int, ii > a, pair <int, ii > b) { if (a.ss.ff != b.ss.ff) return a.ss.ff < b.ss.ff; return a.ff < b.ff; } // DisjointSet int find_parent(int i) { if (p[i] == i) return i; return p[i] = find_parent(p[i]); } void set_lvl(int v, int l) { lvl[v] = l; if (v > N) { set_lvl(ll[v], l + 1); set_lvl(rr[v], l + 1); } } // LeastCommonAncestor void build_lca() { for (int i = 1; i < 20; i++) for (int v = 1; v <= K; v++) { parent[v][i] = parent[parent[v][i - 1]][i - 1]; } } int LCA(int u, int v) { if (lvl[u] > lvl[v]) swap(u, v); for (int i = 20; i > 0; i--) if (lvl[parent[v][i-1]] >= lvl[u]) v = parent[v][i-1]; if (u == v) return u; for (int i = 20; i > 0; i--) if (parent[u][i-1] != parent[v][i-1]) { u = parent[u][i-1]; v = parent[v][i-1]; } return parent[u][0]; } class STO { public: int n, m; STO() { n = m = 0; } void add_color(int x) { a[++n] = x; } void add_query(pair<int, ii > query) { q[++m] = query; } void solve() { sort(q + 1, q + m + 1, mycmp); for (int i=1,j=1; i<=m; i++) { while(j <= q[i].ss.ff) { if (!used[a[j]]) { Update(1, 1, n, j, 1); used[a[j]] = j; } else { Update(1, 1, n, used[a[j]], 0); Update(1, 1, n, j, 1); used[a[j]] = j; } j++; } ans[q[i].ss.ss] = Find(1, 1, n, q[i].ff, q[i].ss.ff); } } int get_ans(int i) { return ans[i]; } int Find(int ind, int A, int B, int l, int r) { if (l > B || r < A) return 0; if (A == l && B == r) return st[ind]; int mid = (A + B) / 2; return Find(ind * 2, A, mid, l, min(mid, r)) + Find(ind * 2 + 1, mid + 1, B, max(mid + 1, l), r); } void Update(int ind, int l, int r, int x, int d) { if (l == r) st[ind] = d; else { int mid = (l + r) / 2; if (x <= mid) Update(ind * 2, l, mid, x, d); else Update(ind * 2 + 1, mid + 1, r, x, d); st[ind] = st[ind * 2] + st[ind * 2 + 1]; } } }; STO seg_tree; void dfs(int v) { if (v > N) { dfs(ll[v]); dfs(rr[v]); L[v] = L[ll[v]]; R[v] = R[rr[v]]; seg_tree.add_query(mp(L[v], mp(R[v], qq))); qq++; } else { C++; seg_tree.add_color(col[v]); L[v] = C; R[v] = C; } } void dfs1(int v) { if (v == 0) return; if (v > N) { dfs1(ll[v]); dfs1(rr[v]); weight[v] = seg_tree.get_ans(qq); qq++; } else weight[v] = 1; } void color_solve() { vector<int> v1, v2; for (int i = 1; i <= N; i++) v1.pb(T[i]); sort(v1.begin(), v1.end()); v2.pb(v1[0]); for (int i = 1, sz = 0; i<v1.size(); i++) if (v2[sz - 1] != v1[i]) { v2.pb(v1[i]); sz++; } for (int i = 1; i <= N; i++) col[i] = lower_bound(v2.begin(), v2.end(), T[i]) - v2.begin() + 1; } int main() { int u, v, e, k, x, y; scanf("%d%d%d",&N,&M,&Q); for (int i = 1; i <= N; i++) { scanf("%d",&T[i]); G[0].pb(mp(i, -max_edge)); G[i].pb(mp(0, -max_edge)); } for (int j = 0; j < M; j++) { scanf("%d%d%d",&u,&v,&e); G[u].pb(mp(v, -e)); G[v].pb(mp(u, -e)); } pq.push(mp(0, mp(0, -1))); while (!pq.empty()) { e = pq.top().ff; x = pq.top().ss.ff; y = pq.top().ss.ss; pq.pop(); if (!vis[x]) { vis[x] = true; if (y != -1) E.pb(mp(-e, mp(x, y))); for (int i = 0; i < G[x].size(); i++) if (!vis[G[x][i].ff]) pq.push(mp(G[x][i].ss, mp(G[x][i].ff, x))); } } sort(E.begin(), E.end()); for (int i = 0; i < 2 * N; i++) p[i] = i; K = N; for (int i = 0; i < E.size(); i++) { K++; int X = find_parent(E[i].ss.ff), Y = find_parent(E[i].ss.ss); p[X] = p[Y] = parent[X][0] = parent[Y][0] = K; dis[K] = E[i].ff == max_edge?-1:E[i].ff; ll[K] = X; rr[K] = Y; } color_solve(); qq=1; dfs (K); seg_tree.solve(); qq=1; dfs1(K); set_lvl(K, 1); lvl[0] = parent[0][0] = 0; build_lca(); while (Q--) { scanf("%d%d%d",&x,&y,&k); if (weight[K] < k) { printf("-1n"); continue; } x = LCA(x, y); if (weight[x] >= k) printf("%dn",dis[x]); else { for (int i = 19; i >= 0; i--) { y = parent[x][i]; if (y && weight[y] < k) x = y; } printf("%dn",dis[parent[x][0]]); } } return 0; } {“mode”:”full”,”isActive”:false} Problem solution in C. #include <stdio.h> #include <stdlib.h> typedef struct _tree_node{ enum {red,black} colour; int data; int idx; struct _tree_node *left,*right,*parent; }tree_node; tree_node *get_min(tree_node *root); void merge(tree_node *root,tree_node **m,int *s,int f); int get_group(int x); void update_group(int x,int y); void sort_a3(int*a,int*b,int*c,int size); void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size); void left_rotate(tree_node **root,tree_node *x); void right_rotate(tree_node **root,tree_node *y); void reconstruct(tree_node **root,tree_node *x); int normal_insert(tree_node **root,tree_node *x,int f); int insert(tree_node **root,tree_node *x,int f); void delete(tree_node **root,tree_node *head,int data); int t[100000],x[100000],y[100000],u[100000],q1[100000],q2[100000],q3[100000],ans[100000],g[100000],s[100000],s2[100000],s3[100000],qf[100000]; tree_node *color[100000],*head[100000],*query[100000]; int main(){ int n,m,q,g1,g2,g3,g4,temp,temp2,temp3,i; tree_node *p,*p2,**p3,*p4,*nxt; scanf("%d%d%d",&n,&m,&q); for(i=0;i<n;i++) scanf("%d",t+i); for(i=0;i<m;i++){ scanf("%d%d%d",x+i,y+i,u+i); x[i]--; y[i]--; } for(i=0;i<q;i++){ scanf("%d%d%d",q1+i,q2+i,q3+i); q1[i]--; q2[i]--; ans[i]=-1; } sort_a3(u,x,y,m); for(i=0;i<n;i++){ g[i]=i; p=(tree_node*)malloc(sizeof(tree_node)); p->data=t[i]; p->left=p->right=p->parent=NULL; insert(color+i,p,0); s[i]=1; } for(i=0;i<q;i++) if(q1[i]==q2[i]){ p=(tree_node*)malloc(sizeof(tree_node)); p->data=q3[i]; p->idx=i; p->left=p->right=p->parent=NULL; insert(&query[q1[i]],p,0); s3[q1[i]]++; } else{ p=(tree_node*)malloc(sizeof(tree_node)); p->data=q3[i]; p->idx=i; p->left=head[q1[i]]; head[q1[i]]=p; s2[q1[i]]++; p=(tree_node*)malloc(sizeof(tree_node)); p->data=q3[i]; p->idx=i; p->left=head[q2[i]]; head[q2[i]]=p; s2[q2[i]]++; } for(i=0;i<m;i++){ g1=get_group(x[i]); g2=get_group(y[i]); if(g1==g2) continue; if(s[g1]<s[g2]){ merge(color[g1],&color[g2],&s[g2],1); p=color[g2]; temp=s[g2]; } else{ merge(color[g2],&color[g1],&s[g1],1); p=color[g1]; temp=s[g1]; } if(s2[g1]<s2[g2]){ for(p2=head[g1];p2;p2=nxt){ nxt=p2->left; g3=get_group(q1[p2->idx]); g4=get_group(q2[p2->idx]); if(!qf[p2->idx]){ if((g3==g1 && g4==g2) || (g3==g2 && g4==g1)){ qf[p2->idx]=1; p2->left=p2->right=p2->parent=NULL; insert(&query[g1],p2,0); s3[g1]++; } else{ p2->left=head[g2]; head[g2]=p2; s2[g2]++; } } } p2=head[g2]; temp2=s2[g2]; } else{ for(p2=head[g2];p2;p2=nxt){ nxt=p2->left; g3=get_group(q1[p2->idx]); g4=get_group(q2[p2->idx]); if(!qf[p2->idx]){ if((g3==g1 && g4==g2) || (g3==g2 && g4==g1)){ qf[p2->idx]=1; p2->left=p2->right=p2->parent=NULL; insert(&query[g2],p2,0); s3[g2]++; } else{ p2->left=head[g1]; head[g1]=p2; s2[g1]++; } } } p2=head[g1]; temp2=s2[g1]; } if(s3[g1]<s3[g2]){ merge(query[g1],&query[g2],&s3[g2],0); p3=&query[g2]; temp3=s3[g2]; } else{ merge(query[g2],&query[g1],&s3[g1],0); p3=&query[g1]; temp3=s3[g1]; } while(1){ if(!temp3) break; p4=get_min(*p3); if(p4->data>temp) break; ans[p4->idx]=u[i]; delete(p3,*p3,p4->data); temp3--; } update_group(x[i],g1); update_group(y[i],g1); s[g1]=temp; s2[g1]=temp2; s3[g1]=temp3; color[g1]=p; head[g1]=p2; query[g1]=*p3; } for(i=0;i<q;i++){ if(q1[i]==q2[i] && q3[i]==1) ans[i]=0; printf("%dn",ans[i]); } return 0; } tree_node *get_min(tree_node *root){ if(!root) return NULL; if(root->left) return get_min(root->left); return root; } void merge(tree_node *root,tree_node **m,int *s,int f){ if(!root) return; merge(root->left,m,s,f); merge(root->right,m,s,f); root->left=root->right=root->parent=NULL; (*s)+=insert(m,root,f); return; } int get_group(int x){ while(g[x]!=x) x=g[x]; return x; } void update_group(int x,int y){ int z=-1; while(1){ if(x==z) break; z=x; x=g[x]; g[z]=y; } return; } void sort_a3(int*a,int*b,int*c,int size){ if (size < 2) return; int m = (size+1)/2,i; int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c; 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)); 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_b[i]=b[i]; left_c[i]=c[i]; } for(i=0;i<size-m;i++){ right_a[i]=a[i+m]; right_b[i]=b[i+m]; right_c[i]=c[i+m]; } sort_a3(left_a,left_b,left_c,m); sort_a3(right_a,right_b,right_c,size-m); merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m); free(left_a); free(right_a); free(left_b); free(right_b); free(left_c); free(right_c); return; } void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,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]; c[i+j] = right_c[j]; j++; } else if (j == right_size) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; c[i+j] = left_c[i]; i++; } else if (left_a[i] <= right_a[j]) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; c[i+j] = left_c[i]; i++; } else { a[i+j] = right_a[j]; b[i+j] = right_b[j]; c[i+j] = right_c[j]; j++; } } return; } void left_rotate(tree_node **root,tree_node *x){ tree_node *y; y=x->right; if(!y) return; x->right=y->left; if(y->left) y->left->parent=x; y->parent=x->parent; if(x->parent==NULL) *root=y; else if(x==x->parent->left) x->parent->left=y; else x->parent->right=y; y->left=x; x->parent=y; return; } void right_rotate(tree_node **root,tree_node *y){ tree_node *x; x=y->left; if(!x) return; y->left=x->right; if(x->right) x->right->parent=y; x->parent=y->parent; if(y->parent==NULL) *root=x; else if(y==y->parent->right) y->parent->right=x; else y->parent->left=x; x->right=y; y->parent=x; return; } void reconstruct(tree_node **root,tree_node *x){ tree_node *y,*z; y=x->parent; z=x->parent->parent; x->colour=black; z->colour=red; x->parent=z->parent; if(z->parent==NULL) *root=x; else if(z==z->parent->left) z->parent->left=x; else z->parent->right=x; if(z->left==y){ x->left=y; x->right=z; } else{ x->left=z; x->right=y; } y->parent=z->parent=x; y->left=y->right=z->left=z->right=NULL; return; } int normal_insert(tree_node **root,tree_node *x,int f){ if(*root==NULL) *root=x; else if(f && (*root)->data==x->data) return 0; else{ x->parent=*root; if((*root)->data>x->data) return normal_insert(&((*root)->left),x,f); else return normal_insert(&((*root)->right),x,f); } return 1; } int insert(tree_node **root,tree_node *x,int f){ if(!normal_insert(root,x,f)) return 0; tree_node *y; x->colour=red; while(x!=*root && x->parent->colour==red){ if(x->parent==x->parent->parent->left){ y=x->parent->parent->right; if(!y) if(x==x->parent->left){ x->parent->colour=black; x->parent->parent->colour=red; right_rotate(root,x->parent->parent); } else{ y=x->parent; reconstruct(root,x); x=y; } else if(y->colour==red){ x->parent->colour=black; y->colour=black; x->parent->parent->colour=red; x=x->parent->parent; } else{ if(x==x->parent->right){ x=x->parent; left_rotate(root,x); } x->parent->colour=black; x->parent->parent->colour=red; right_rotate(root,x->parent->parent); } } else{ y=x->parent->parent->left; if(!y) if(x==x->parent->right){ x->parent->colour=black; x->parent->parent->colour=red; left_rotate(root,x->parent->parent); } else{ y=x->parent; reconstruct(root,x); x=y; } else if(y->colour==red){ x->parent->colour=black; y->colour=black; x->parent->parent->colour=red; x=x->parent->parent; } else{ if(x==x->parent->left){ x=x->parent; right_rotate(root,x); } x->parent->colour=black; x->parent->parent->colour=red; left_rotate(root,x->parent->parent); } } } (*root)->colour=black; return 1; } void delete(tree_node **root,tree_node *head,int data){ tree_node *db,*parent,*brother,*child,none; if(!head) return; if(data<head->data || (data==head->data && head->left)){ delete(root,head->left,data); return; } if(data>head->data){ delete(root,head->right,data); return; } if(data==head->data){ if(head->left && head->right){ db=head->right; while(db->left) db=db->left; head->data=db->data; // Do node copy here. head->idx=db->idx; head=db; } if(head->left==NULL && head->right==NULL){ parent=head->parent; if(!parent){ *root=NULL; free(head); return; } brother=(parent->left==head)?parent->right:parent->left; if(head->colour==red){ if(parent->left==head) parent->left=NULL; else parent->right=NULL; free(head); return; } if(parent->left==head) parent->left=&none; else parent->right=&none; none.parent=parent; none.colour=black; db=&none; free(head); } else{ parent=head->parent; child=(!head->left)?head->right:head->left; if(!parent){ *root=child; child->parent=NULL; child->colour=black; free(head); return; } if(parent->left==head) parent->left=child; else parent->right=child; child->parent=parent; db=child; free(head); } } while(db){ if(db->colour==red){ db->colour=black; return; } if(db==*root) return; parent=db->parent; brother=(parent->left==db)?parent->right:parent->left; if(!brother) db=parent; else if(brother==parent->right){ if(brother->colour==black && brother->right && brother->right->colour==red){ brother->colour=parent->colour; brother->right->colour=black; parent->colour=black; left_rotate(root,parent); if(db==&none) parent->left=NULL; return; } else if(brother->colour==black && brother->left && brother->left->colour==red){ brother->left->colour=parent->colour; parent->colour=black; right_rotate(root,brother); left_rotate(root,parent); if(db==&none) parent->left=NULL; return; } else if(brother->colour==black){ brother->colour=red; if(db==&none) parent->left=NULL; db=parent; } else{ brother->colour=black; parent->colour=red; left_rotate(root,parent); } } else{ if(brother->colour==black && brother->left && brother->left->colour==red){ brother->colour=parent->colour; brother->left->colour=black; parent->colour=black; right_rotate(root,parent); if(db==&none) parent->right=NULL; return; } else if(brother->colour==black && brother->right && brother->right->colour==red){ brother->right->colour=parent->colour; parent->colour=black; left_rotate(root,brother); right_rotate(root,parent); if(db==&none) parent->right=NULL; return; } else if(brother->colour==black){ brother->colour=red; if(db==&none) parent->right=NULL; db=parent; } else{ brother->colour=black; parent->colour=red; right_rotate(root,parent); } } } return; } {“mode”:”full”,”isActive”:false} Algorithms coding problems solutions