Taha1506's blog

By Taha1506, history, 3 years ago, In English

I was studing cp-algorithem web and I was trying to come up with 0-1 BFS by my self.I came up with the following algorithm:

We run a DSU to all edges with weight $$$0$$$ after that we come up with some components now for each edge with weight $$$1$$$ instead of adding edges between the original vertices $$$u,v$$$ we add edges between their leaders then apply a BFS to the leaders(with source vertex being the leader vertex of our source-vertex) only then the length of the path between $$$u$$$ and some source-vertex $$$v$$$ will be the length between leader of $$$v,u$$$.

This is probably not new.But I was wondering if this is faster or slower than the actual 0-1 BFS in CP?In terms of time complexity it is worse than the actual 0-1 BFS but since in competetive programming we are dealing with small numbers $$$\alpha (m,n)$$$ may be treated as a constant.Any idea on how to test this?

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