The problem is to find if a given edge `(a, b)`

is connected in a graph with vertices `{a, b, c, ...}`

.

### Naive Solution – O(n^2)

- Maintain a parent array of size (len of vertex array)
- Update an edge (a, b) with the index a & b in the vertex array

```
ParentArray[a] = b
ParentArray[b] = b
```

### Code

```
class Solution(object):
def __init__(self, nodesCount):
self.nodes = list(range(nodesCount + 1))
def union(self, p, q):
currentRoot = self.root(p)
for index, num in enumerate(self.nodes):
if num == currentRoot:
self.nodes[index] = q
print(self.nodes)
def find(self, p, q):
return self.root(p) == self.root(q)
def root(self, p):
return self.nodes[p]
if __name__ == "__main__":
s = Solution(6)
s.union(1, 2)
s.union(2, 3)
s.union(2, 4)
print(s.find(1, 3))
print(s.find(3, 4))
print(s.find(3, 6))
```

### Execution

```
$ python union-find.py
[0, 2, 2, 3, 4, 5, 6]
[0, 3, 3, 3, 4, 5, 6]
[0, 4, 4, 4, 4, 5, 6]
True
True
False
```

Written with StackEdit.