Taha1506's blog

By Taha1506, history, 3 months ago,

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?

• +15