"Firehouse" Problem

If you have an undirected, unweighted graph G, and a marked subset of points called 'Firehouses,' is there an O(n+m) algorithm to find every vertex's closes firehouse?

I can only come up with O(n^2) stuff. Although I do like the idea of repeatedly raising the adjacency matrix to a power n, until every vertex has a nonzero entry :P

>>18

That's not good enough. I think I might have gotten it though.

You're not allowed to know which are firehouses until you visit the points so here's what I came up with.

Initialize every vertex's distance to 0.
Begin a standard depth first search on any vertex v.
Until the first firehouse is found, add 1 to the distance of each vertex you have visited.

When the first firehouse is found, keep it's distance to zero, and then continue the depth first search, assigning the distance as the minimum of its parent's distance+1, or any of it's backedges+1.

I think that works in O(n+m) time.