We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Subset Component
  5. Discussions

Subset Component

  • cpcbordeaux
     + 1 comment

    python solution

    def formatbin(s): return '{:b}'.format(s)

def findConnectedComponents(d):
    # Write your code here
    
    # generate power set
    i = 1 << len(d)
    count = 0
    for s in range(i):
        # get current subset of powerset using bits of s to indicate if
        # ith element of d is in the subset
        ss = [n for ind,n in enumerate(d) if (1<<ind) & s != 0]
        #print(s, 'ss', ss)
        
        verts = 0
        connectedcount = 0
        for e in ss:
            # skip if power of 2 or zero, won't contribute to connections
            if (formatbin(e).count('1') - 1 if e else 0) < 1:
                continue
            # check if new connected component has been found
            if not verts & e:
                #print('new connected component', formatbin(verts), formatbin(e))
                connectedcount += 1
            # update running vertices with connections
            verts |= e
        # get vertex count that contribute to connections
        vertcount = formatbin(verts).count('1')
        
        #print('verts', formatbin(verts), 'connectedcount', connectedcount, 'vertcount', vertcount)
        
        # update count
        sscount = 64 - vertcount + connectedcount
        count += sscount
        
        #print(sscount)
    
    return count
    1. loop through power set
      • this can be done by looping through [0, 2^n) and using the bits of the current value to indicate which indices of the number list define the current subset
    2. loop through elements in current subset while keeping track of vertices that contribute to connections (have an edge with another vertex) and the count of connected components (with edges)
    3. the number of total components in the graph for the given subset will be: total number of possible graphs - verts in connections + connected components (with edges)

    really thought this would be way too slow until I saw that O(n^2 * 2^n) was ok