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: MEDIUM

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


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):

	def __init__(self, n):
		self.links = [[] for i in range(n)]

	def union(self, p, q):
		for [x, y] in [[p, q], [q, p]]:
			self.links[x].append(y)

	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):

	def __init__(self, n):
		self.a = []

	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]

	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):
		self.clusters = {}

	def union(self, p, q):
		pp = self.clusters.get(p, None)
		qq = self.clusters.get(q, None)
		if pp and qq:
			pp |= qq
			for c in qq:
				self.clusters[c] = pp
		elif pp:
			self.clusters[p].add(q)
			self.clusters[q] = self.clusters[p]
		elif qq:
			self.clusters[q].add(p)
			self.clusters[p] = self.clusters[q]
		else:
			pq = {p, q}
			self.clusters[p] = pq
			self.clusters[q] = pq

	def connected(self, p, q):
		return q in self.clusters.get(p, {})