Intro

Imagine you are building a social network from scratch. Initially, you have $N$ people, but zero friendships. Everyone is a stranger.

Then, events happen in real-time: "User $1$ becomes friends with User $2$." "User $3$ becomes friends with User $4$." "User $1$ becomes friends with User $3$." After every event, you might want to ask: "Are User $2$ and User $4$ connected?" Running BFS after every single added edge is too slow ($O(N+E)$ every time). You need something faster.