Given nodes initially disconnected, handle:
link u v: Add edge between u and v (guaranteed no cycle)cut u v: Remove edge between u and v (guaranteed exists)connected u v: Are u and v in the same component?
Here's the core dynamic forest connectivity problem. Note: This assumes the graph stays a forest (no cycles). General dynamic connectivity (allowing cycles) requires different techniques.