gXa's blog

By gXa, history, 5 years ago, In English

A graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted edges given in K. If it creates a path, we have to discard the edge.

Example: N = 4; K = {(1, 4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)

  • Vote: I like it
  • -14
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

So what does the question ask? The set of edges cannot be added?