0

The description of the question is the following.

A program would read a file by lines to build up a graph. Each line in the file would be one of theses three kinds of operations:

  1. add x y, which means adding an edge between node x and y,so that a graph would be formed. This graph is a undirected graph.
  2. remove x y, which means removing an edge between node x and y, if it's not valid(x or y does not appear to exist in graph or not edges exists between x and y), then do nothing.
  3. is linked x y, which should return if x and y can be connected through all the edges in the graph. The time complexity of this operation should be constant time.

Here is an example:

   add 1 2  
   add 2 3
   is linked 1 3(should be true ,cause there is a path 1-> 2, 2->3)
   add 3 4
   remove 2 3
   is linked 1 4(should be false)
Cœur
  • 37,241
  • 25
  • 195
  • 267
Guangyi Tao
  • 11
  • 1
  • I don't understand what you are asking. Edit your post to clarify it. – nbro Mar 13 '18 at 17:10
  • Look for connected component ? Do you have the specifications of the connected component to search for ? Or do you just want to see if the graph has 'n' number of connected components ? Do you want this in constant time ? I don't think so. – SomeDude Mar 13 '18 at 18:02
  • Do you have any time constraints on the add and remove operations? Otherwise you could just build a Boolean connectivity matrix each time you update the graph. Checking for connectivity is then possible in constant time with the cost of add and remove going up. – SaiBot Mar 14 '18 at 11:15
  • https://stackoverflow.com/a/73504595/4393351 – KushalSeth Aug 26 '22 at 17:24

1 Answers1

1

You can use union-find data structure to do that in amortized time of near linear. For its structure and implementation details you can google the union by rank with path compression. You can find many academic notes about that with pictorial tutorials and precise time/space-complexity analysis. This link and this one can help.

But two notes here:

Its complexity is amortized. See here if you want to compare it with worst-case analysis.

What means near linear? The amortized analysis of the algorithm is equal to inverse Ackermann function noted by α ( n ).

where α ( n ) {\displaystyle \alpha (n)} \alpha (n) is the inverse Ackermann function. This function has a value α ( n ) < 5 {\displaystyle \alpha (n)<5} {\displaystyle \alpha (n)<5} for any value of n that can be written in this physical universe, so the disjoint-set operations take place in essentially constant time

Bonje Fir
  • 787
  • 8
  • 25