In this HackerRank Subset Component problem solution You are given an array with n 64-bit integers:d[0],d[1],…,d[n-1]. BIT(x, i) = (x >> i) & 1, where B(x,i) is the ith lower bit of x in binary form. If we regard every bit as a vertex of a graph G, there is an undirected edge between vertices i and j if there is a value k such that BIT(d[k], i) == 1 && BIT(d[k], j) == 1. For every subset of the input array, how many connected components are there in that graph? A connected component in a graph is a set of nodes that are accessible to each other via a path of edges. There may be multiple connected components in a graph.
Problem solution in Python.
#!/bin/python3 import math import os import random import re import sys # Complete the findConnectedComponents function below. def count_components(i, prev_components, cliques): ''' Back-tracking algorithm ''' if i >= len(cliques): return len(prev_components) c = count_components(i+1, prev_components, cliques) # now add a clique new_comp = cliques[i] components = [] for comp in prev_components: if comp & new_comp: new_comp |= comp else: components.append(comp) if new_comp: components.append(new_comp) c += count_components(i+1, components, cliques) return c if __name__ == '__main__': n = int(input().strip()) d = input().strip().split() d = [int(v) for v in d] assert len(d) == n singletons = [1<<j for j in range(64)] print(count_components(0, singletons, d))
Problem solution in Java.
import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; public class Solution { private static int findConnectedComponents(long[] nums) { Result result = new Result(); int n = nums.length; UF[] mem = new UF[0x000F_FFFF + 1]; mem[0] = new UF(64); generateAndAdd(0, n, nums, 0, mem, result); return result.sum; } private static void generateAndAdd(int i, int n, long[] nums, int indices, UF[] mem, Result result) { if (i == n) { if (indices == 0) { result.sum += mem[0].components; return; } int index = 19; while (index >= 0 && ((1 << index) & indices) == 0) { index--; } mem[indices] = new UF(mem[indices & ~(1 << index)]); for (int l = 0; l < 63; l++) { if ((nums[index] & (1l << l)) == 0) { continue; } for (int h = l + 1; h < 64; h++) { if ((nums[index] & (1l << h)) > 0) { mem[indices].union(l, h); } } } //System.out.println("sum = " + mem[indices].components); result.sum += mem[indices].components; return; } // no add generateAndAdd(i + 1, n, nums, indices, mem, result); // with add indices |= (1 << i); generateAndAdd(i + 1, n, nums, indices, mem, result); indices &= ~(1 << i); } private static class Result { private int sum = 0; } private static class UF { int[] uf; int[] size; int n; int components; private UF(int n) { this.n = n; uf = new int[n]; size = new int[n]; components = n; for (int i = 0; i < n; i++) { uf[i] = i; size[i] = 1; } } private UF(UF other) { this.n = other.n; uf = new int[this.n]; size = new int[this.n]; components = other.components; for (int i = 0; i < this.n; i++) { uf[i] = other.uf[i]; size[i] = other.size[i]; } } private boolean union(int i, int j) { int iRoot = root(i); int jRoot = root(j); if (iRoot == jRoot) { return false; } components--; if (size[iRoot] <= size[jRoot]) { uf[iRoot] = jRoot; size[jRoot] += size[iRoot]; } else { uf[jRoot] = iRoot; size[iRoot] += size[jRoot]; } return true; } private int root(int i) { while (uf[i] != i) { i = uf[i]; } return i; } } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int dCount = scanner.nextInt(); scanner.skip("(rn|[nru2028u2029u0085])?"); long[] d = new long[dCount]; String[] dItems = scanner.nextLine().split(" "); scanner.skip("(rn|[nru2028u2029u0085])?"); for (int i = 0; i < dCount; i++) { long dItem = Long.parseLong(dItems[i]); d[i] = dItem; } int components = findConnectedComponents(d); bufferedWriter.write(String.valueOf(components)); bufferedWriter.newLine(); bufferedWriter.close(); scanner.close(); } }
Problem solution in C++.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <cstdint> #include <cstring> #include <memory> using namespace std; static const int BITS = 64; class Num { private: struct Component { int parent; int h; }; Component cs[BITS]; int getparent(int i) { if (i == cs[i].parent) return i; return cs[i].parent = getparent(cs[i].parent); } void join(int a, int b) { a = getparent(a); b = getparent(b); if (a == b) return; if (cs[a].h > cs[b].h) { cs[b].parent = a; } else if (cs[a].h < cs[b].h) { cs[a].parent = b; } else { cs[b].parent = a; ++cs[a].h; } } public: Num(uint64_t x) { for (int i = 0; i < BITS; ++i) { cs[i].parent = i; cs[i].h = 1; } for (int i = 0; i < BITS; ++i) for (int j = 0; j < BITS; ++j) if ((x >> i) & 1 == 1 & (x >> j) & 1 == 1) join(i, j); } Num& operator=(const Num& other) { memcpy(cs, other.cs, sizeof(cs)); return *this; } Num (const Num &other) { *this = other; } int components() const { int result = 0; for (int i = 0; i < BITS; ++i) if (cs[i].parent == i) ++result; return result; } void sum(const Num &other) { for (int i = 0; i < BITS; ++i) join(i, other.cs[i].parent); } }; template<typename T> class Restorer { private: T orig; T &ref; Restorer(const Restorer &); Restorer &operator=(const Restorer &); public: Restorer(T &obj) : orig(obj) , ref(obj) { } void restore() { ref = orig; } }; void backtrack(int &result, Num &state, const vector<shared_ptr<Num> > &ns, int idx) { if (idx == ns.size()) { result += state.components(); return; } Restorer<Num> rest(state); backtrack(result, state, ns, idx+1); rest.restore(); state.sum(*ns[idx]); backtrack(result, state, ns, idx+1); rest.restore(); } int main() { int n; vector<shared_ptr<Num> > ns; for (cin >> n; n > 0; --n) { uint64_t x; cin >> x; ns.push_back(shared_ptr<Num>(new Num(x))); } int result = 0; Num empty(0); backtrack(result, empty, ns, 0); cout << result << 'n'; return 0; }
Problem solution in C.
#include <assert.h> #include <limits.h> #include <math.h> #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #define SIZE 64 char* readline(); char** split_string(char*); struct cpntlist{ long cpnts[SIZE]; }; // Complete the findConnectedComponents function below. int findConnectedComponents(int d_count, long* d) { int toreturn = SIZE; struct cpntlist *cpnts = malloc(sizeof(struct cpntlist)<<d_count); for(int i = 0; i < SIZE; i++){ cpnts[0].cpnts[i] = ((long)1)<<i; } for(int i = 0; i < d_count; i++){ long mask = d[i]; for(int j = 0; j < 1<<i; j++){ struct cpntlist oldlist = cpnts[j]; int firstcpnt = -1; int next = (1<<i) + j; int numcpnts = 0; for(int k = 0; k < SIZE; k++){ if((mask&oldlist.cpnts[k]) != 0){ if(firstcpnt == -1){ firstcpnt = k; cpnts[next].cpnts[k] = oldlist.cpnts[k]; numcpnts++; } else{ cpnts[next].cpnts[firstcpnt] |= oldlist.cpnts[k]; cpnts[next].cpnts[k] = 0; } } else if(oldlist.cpnts[k] != 0){ cpnts[next].cpnts[k] = oldlist.cpnts[k]; numcpnts++; } else{ cpnts[next].cpnts[k] = 0; } } toreturn += numcpnts; } } return toreturn; } int main() { FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); char* d_count_endptr; char* d_count_str = readline(); int d_count = strtol(d_count_str, &d_count_endptr, 10); if (d_count_endptr == d_count_str || *d_count_endptr != ' ') { exit(EXIT_FAILURE); } char** d_temp = split_string(readline()); long* d = malloc(d_count * sizeof(long)); for (int i = 0; i < d_count; i++) { char* d_item_endptr; char* d_item_str = *(d_temp + i); long d_item = strtol(d_item_str, &d_item_endptr, 10); if (d_item_endptr == d_item_str || *d_item_endptr != ' ') { exit(EXIT_FAILURE); } *(d + i) = d_item; } int components = findConnectedComponents(d_count, d); fprintf(fptr, "%dn", components); fclose(fptr); return 0; } char* readline() { size_t alloc_length = 1024; size_t data_length = 0; char* data = malloc(alloc_length); while (true) { char* cursor = data + data_length; char* line = fgets(cursor, alloc_length - data_length, stdin); if (!line) { break; } data_length += strlen(cursor); if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; } size_t new_length = alloc_length << 1; data = realloc(data, new_length); if (!data) { break; } alloc_length = new_length; } if (data[data_length - 1] == 'n') { data[data_length - 1] = ' '; } if(data[data_length - 1] != ' '){ data_length++; data = realloc(data, data_length); data[data_length - 1] = ' '; } data = realloc(data, data_length); return data; } char** split_string(char* str) { char** splits = NULL; char* token = strtok(str, " "); int spaces = 0; while (token) { splits = realloc(splits, sizeof(char*) * ++spaces); if (!splits) { return splits; } splits[spaces - 1] = token; token = strtok(NULL, " "); } return splits; }