Detecting connectedness of nodes over a long time in a graph

Question

I start out with a graph of N nodes with no edges.

Then I procede to take M predetermined steps.

At each step, I must either create an edge between two nodes, or delete an edge.

After each step, I must print out how many connected components there are in my graph.

Is there an algorithm for solving this problem in time linear with respect to M? If not, is there one better than O(min(M,N) * M) in the worst case?

EDIT:

The program does not get to decide what the M steps are.

I have to read from the input, whether I am supposed to create an edge or delete it, and also which edge I am supposed to create/delete.

So example input might be

N = 4
M = 4
JOIN 1 2
JOIN 2 3
DELETE 2 3
DELETE 1 2

Then my output should be

3 # (1 2) 3 4
2 # (1 2 3) 4
3 # (1 2) 3 4
4 # 1 2 3 4

Answer 1

There are ways to solve this problem fully online, but they're more complicated than this answer. The algorithm that I'm proposing is to maintain a spanning forest of the available edges, together with the number of components of the spanning forest (and hence the graph). If we were attacking this problem fully online, then this would be problematic, since a spanning forest edge might get deleted, leaving us to paw through the unused edges for a replacement. We know, however, how soon each edge currently in the graph will be deleted.

The particular spanning forest that we maintain is a maximum-weight spanning forest, where the weight of each edge is its deletion time. If an edge belonging to this spanning forest is deleted, then there is no replacement, since every other edge connecting the components represented by its endpoints either hasn't been inserted yet or, having lesser weight, has already been deleted.

There's a dynamic tree data structure, also referred to as a link/cut tree, due to Sleator and Tarjan, that can be made to provide the following operations in logarithmic time.

Link(u, v, w) - inserts an edge between u and v with weight w;
                u and v must not be connected already

Cut(u, v) - cuts the edge between u and v, if it exists;
            returns a boolean indicating whether an edge was removed

FindMin(u, v) - finds the minimum-weight edge on the path from u to v
                  and returns its endpoints and weight;
                returns null if either u = v or u and v are not connected

To maintain the forest, when an edge from u to v is inserted, compare its removal time to the minimum on the path from u to v. If the minimum does not exist, then insert the edge. If the minimum is less than the new edge, delete the minimum and replace it with the new edge. Otherwise, do nothing. When an edge from u to v is deleted, attempt to delete it from the forest.

The running time of this approach is O(m log n). If you don't have a dynamic tree handy, then it admittedly will take quite a while to implement. Instead of using a proper dynamic tree, I've had success with a much simpler data structure that just stores the forest as a bunch of nodes with weights and parent pointers. The running time then is O(m d) where d is the maximum diameter of the graph, and if you're lucky, d is quite a lot less than n.