# Dynamic connectivity

- Dynamic connectivity refers to a data structure that dynamically reflects information about connections between vertices within a graph
- In this data structure:
- the set of vertices
`V`

is fixed - the set of edges
`E`

can change

- the set of vertices
- Types of dynamic connectivity:
**incremental**: edges are*only added*to the graph**decremental**: edges are*only removed*from the graph**fully dynamic**: edges are*added or removed*

- The dynamic connectivity structure should provide quick answers to the question
*“is there a path between*`x`

and`y`

?”- AKA, "do vertices
`x`

and`y`

belong to the same connected component?

- AKA, "do vertices
- The dynamic connectivity structure should reflect any addition or removal of edges, such that its output is always current with the latest state of the graph it represents

## Example

- Given a set of N objects:
**Union command**: connect two objects**Find/connected query**: check if two given objects are connected

*Build connections:*

```
union(4, 3)
union(3, 8)
union(6, 5)
union(9, 4)
union(2, 1)
```

*Query connections:*

```
connected(0, 7) // false
connected(8, 9) // true
```

*Build more connections:*

```
union(5, 0)
union(7, 2)
union(6, 1)
union(1, 0)
```

*Query again:*

```
connected(0, 7) // now it's true
```