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.
defformatbin(s):return'{:b}'.format(s)deffindConnectedComponents(d):# Write your code here# generate power seti=1<<len(d)count=0forsinrange(i):# get current subset of powerset using bits of s to indicate if# ith element of d is in the subsetss=[nforind,ninenumerate(d)if(1<<ind)&s!=0]#print(s, 'ss', ss)verts=0connectedcount=0foreinss:# skip if power of 2 or zero, won't contribute to connectionsif(formatbin(e).count('1')-1ifeelse0)<1:continue# check if new connected component has been foundifnotverts&e:#print('new connected component', formatbin(verts), formatbin(e))connectedcount+=1# update running vertices with connectionsverts|=e# get vertex count that contribute to connectionsvertcount=formatbin(verts).count('1')#print('verts', formatbin(verts), 'connectedcount', connectedcount, 'vertcount', vertcount)# update countsscount=64-vertcount+connectedcountcount+=sscount#print(sscount)returncount
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
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)
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
Subset Component
You are viewing a single comment's thread. Return to all comments →
python solution
really thought this would be way too slow until I saw that O(n^2 * 2^n) was ok