The Dynamic Connectivity Problem

Given a set of of N objects, is there a path connecting the two objects?

Implement an class that implements the following API:

  *  Takes n as input, initializing a data-structure with N objects (0...N-1)
  *  Implements a Union command that adds a connection between point p and point q
  *  Implements a Connected command that returns a boolean and asks is there a connection between point p and point q

As a simple example: 
Imagine you initialize an data structure filled with integers from 0 to 9 (N = 10)
```python
  results1 = DynamicConnectivity(10)
```
You will receive a series of union commands linking various points
```python
  results1.union(4,3)
  results1.union(3,8)
  results1.union(6,5)
  results1.union(9,4)
  results1.union(2,1)
```
This should result in 5 groups of connections:
  
  * 3,4,8,9
  * 5,6
  * 2,1
  * 0
  * 7

All members of a groups (set) are conected to every other member
If you asked is 0 connected to 7, it should return False
If you asked is 8 connected to 9 you should return True even if 8,9 wern't directly joined.
(8 is connected to 3 which is connected to 4 which is connected to 9)
```python
  results1.connected(0,7) == False
  results1.connected(8,9) == True
```

For the purposes of this problem, you do not have to mainatin the order of the connections, you just have to know that the connection is there.

Hint:
  There is a naive implenetation that takes time proportional to O(n^2) (Quadratic Funtion)
  **This will time out the problem**
  (Because every time you double the input like from 50 nodes to 100 nodes, the function takes **4** times as long)
  Test will check that you are able to outrun this naive implementation. If you can't that means that your code is too slow
  
  There is a solution that takes linearitmic time or faster O(n * lg n)

Hint Two: (Take it or leave it)
  If you find yourself nesting a loop inside a loop, you are creating a quadratic function

Implementation must be able to handle initializing 1 million nodes, and creating connections between those nodes.

Full Tests before submission generate random connections to make sure you can't hard code the connections into your class.

Difficulty: interview

Starter code:

def __init__(self, n):
	

Solutions:
class DynamicConnectivity(object):
    par = []
    def __init__(self, n):
        self.par = [i for i in range(n)]

    def union(self, p, q):
        if self.root(p) != self.root(q):
            self.par[self.root(p)] = q

    def root(self, p):
        pp = p
        while self.par[pp] != pp:
            pp = self.par[pp]
        return pp
        
    def connected(self, p, q):
        return True if self.root(p)==self.root(q) else False


class DynamicConnectivity:
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, p):
        stk = [p]
        rp = self.parents[stk[-1]]
        while rp != stk[-1]:
            stk.append(rp)
            rp = self.parents[rp]
        for i in stk:
            self.parents[i] = rp
        return rp

    def union(self, p, q):
        rp, rq = self.find(p), self.find(q)
        if rp == rq: return
        self.parents[rp] = rq

    def connected(self, p, q):
        return self.find(p) == self.find(q)

class DynamicConnectivity:
    def __init__(self, n):
        self.roots = {}
        self.sizes = {}

    def find_root(self, x):
        if not x in self.roots:
            self.roots[x] = x
            self.sizes[x] = 1
        while x != self.roots[x]:
            self.roots[x] = self.roots[self.roots[x]]
            x = self.roots[x]
        return x

    def union(self, a, b):
        a, b = self.find_root(a), self.find_root(b)
        if a == b:
            return
        if self.sizes[a] < self.sizes[b]:
            a, b = b, a
        self.roots[b] = a
        self.sizes[a] += self.sizes[b]
    
    def connected(self, a, b):
        return self.find_root(a) == self.find_root(b)

class DynamicConnectivity(object):
    def __init__(self, n):
        self.__map = list(range(0, n))
    
    def __root(self, p):
        while p != self.__map[p]:
            self.__map[p] = self.__map[self.__map[p]]
            p = self.__map[p]
        return p
    
    def union(self, p, q):
        self.__map[self.__root(p)] = self.__root(q)
        
    def connected(self, p, q):
        return self.__root(p) == self.__root(q)


import collections;

class DynamicConnectivity(object):
    def __init__(self, n):
        self.map = collections.defaultdict(list)
        
    def union(self, p, q):
        self.map[p].append(q)
        self.map[q].append(p)
        
    def connected(self, p, q):
        handled = set()
        elements = set([p])
        while elements and not q in elements:
            elements = set(n for e in elements for n in self.map[e]).difference(handled)
            handled.update(elements)
        return q in elements

# 10 times faster than naive
class DynamicConnectivity(object):
    def __init__(self, n):
        self.items = {i:{i} for i in range(n)}

    def union(self, p, q):
        if self.items[p] is not self.items[q]:
            for x in self.items[q]:
                self.items[p].add(x)
                self.items[x] = self.items[p]
        
    def connected(self, p, q):
        return q in self.items[p]

class DynamicConnectivity(object):
# class takes the number of objects n as input, 
# and initializes a data structure with objects numbered from 
# 0 to N-1
    def __init__(self, n):
        self.links = [[] for i in range(n)]

# union connects point p with point q
    def union(self, p, q):
        for [x,y] in [[p,q],[q,p]]:
            self.links[x].append(y)
    
# connected checks if point p is connected to point q and returns a boolean
    def connected(self, p, q):
        stack, seen = [p], set()
        while len(stack):
            p = stack.pop()
            if p == q: return True
            if p in seen: continue
            stack += self.links[p]
            seen.add(p)
        return False

class DynamicConnectivity(object):
    def __init__(self, n):
        self.a=[{i} for i in range(n)]
    def union(self, p, q):
        self.a[p] |= self.a[q]
        for i in self.a[q]: self.a[i]=self.a[p]
    def connected(self, p, q):
        return p in self.a[q]

class DynamicConnectivity(object):
# class takes the number of objects n as input, 
# and initializes a data structure with objects numbered from 
# 0 to N-1
    def __init__(self, n):
        self.a = []

# union connects point p with point q
    def union(self, p, q):
        ip = -1
        for k in range(len(self.a)):
            if p in self.a[k]:
                ip = k
                break
        iq = -1
        for k in range(len(self.a)):
            if q in self.a[k]:
                iq = k
                break
        if ip == iq == -1:
            self.a.append({p,q})
        elif ip == -1 and iq != -1:
            self.a[iq].add(p)
        elif iq == -1 and ip != -1:
            self.a[ip].add(q)
        elif ip != -1 and iq != -1 and ip != iq:
            self.a[ip] |= self.a[iq]
            del self.a[iq]

# connected checks if point p is connected to point q and returns a boolean
    def connected(self, p, q):
        ip = -1
        for k in range(len(self.a)):
            if p in self.a[k]:
                ip = k
                break
        return False if ip == -1 else q in self.a[ip]

class DynamicConnectivity(object):
    def __init__(self, n):
        # class takes the number of objects n as input, 
        # and initializes a data structure with objects numbered from 
        # 0 to N-1
        self.clusters = {}

    def union(self, p, q):
        # union connects point p with point q
        pp = self.clusters.get(p, None)
        qq = self.clusters.get(q, None)
        if pp and qq:
            # merge qq into pp
            pp |= qq
            # redirect all qq mappings to pp
            for c in qq:
                self.clusters[c] = pp
        elif pp:
            # extend pp to include q
            self.clusters[p].add(q)
            self.clusters[q] = self.clusters[p]
        elif qq:
            # extend qq to include p
            self.clusters[q].add(p)
            self.clusters[p] = self.clusters[q]
        else:
            # Create new cluster
            pq = {p, q}
            self.clusters[p] = pq
            self.clusters[q] = pq
        
    def connected(self, p, q):
        # connected checks if point p is connected to point q and returns a boolean
        return q in self.clusters.get(p, {})