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.