Thinking of 0-1 BFS in terms of DSU

Revision en1, by Taha1506, 2021-01-09 09:05:16

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?


  Rev. Lang. By When Δ Comment
en1 English Taha1506 2021-01-09 09:05:16 903 Initial revision (published)