M0jo's blog

By M0jo, history, 4 years ago, In English

Hi, everyone

Some directed graph is given. Check the graph for the uniqueness property of the path(for any two vertices v u, there is no more than one simple path with the beginning in u and the end in v). Simple path is a non-empty path whose vertices are all pairwise distinct.

Does anyone know a solution to this problem faster than running BFS from each vertex?

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it