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("(\r\n|[\n\r\u2028\u2029\u0085])?");
long[] d = new long[dCount];
String[] dItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
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 != '\0') { 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 != '\0') { exit(EXIT_FAILURE); }
*(d + i) = d_item;
}
int components = findConnectedComponents(d_count, d);
fprintf(fptr, "%d\n", 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] = '\0';
}
if(data[data_length - 1] != '\0'){
data_length++;
data = realloc(data, data_length);
data[data_length - 1] = '\0';
}
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;
}
0 Comments