• + 0 comments

    Java8 - using bitwise operations

    public static int findConnectedComponents(List<Long> d) {
    
        TreeMap<Long, Integer> bitsMap = new TreeMap<>();
        
        int n = d.size();
        int numOfSubsets = 1 << n;
        int res = 0;
        
        for (int i = 0; i < numOfSubsets; i ++) {
            List<Long> subset = new ArrayList<>();
                    
            for (int j = 0; j < n; j++) {
                
                int mask = 1 << j;
                if ((i & mask) != 0) { 
                    long cur = d.get(j);
                    ListIterator<Long> iter = subset.listIterator();
                    
                    while (iter.hasNext()) {
                        
                        long iterCur = iter.next();
                    
    //iterate current subset and merge all intersected pairs
    //this way there will not be any stragglers left behind
    //even if met with similar cases such as {3, 12, 6} subset:
    //0011
    //1100
    //0110
                        
                        if ((iterCur & cur) != 0) {
                            cur |= iterCur;
                            iter.remove();            
                        }
                    }
                    subset.add(cur);
                            
                    if (bitsMap.get(cur) == null) {
                        bitsMap.put(cur, countBits(cur));
                    }              
                }
            }
    
    //as we have merged all intersected pairs, 
    //the rest are naturally independent components
                
            int components = subset.size();
            
            long subsetRep = 0;
            for (Long l : subset) {
                subsetRep |= l;
            }
            
            Integer countBit = bitsMap.get(subsetRep);
            if (countBit == null) {
                countBit = countBits(subsetRep);
            }
            res += 64 - countBit + components;    
        }
        
        return res;   
    }