Re: [boost] BGL: like transitive_closure, but not exactly

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-14 13:07:32

By the way, I have a solution, and it's probably sufficiently fast for my
purposes:

----- Original Message -----
From: "Swarat Chaudhuri" <swarat_c_at_[hidden]>
Newsgroups: comp.theory
Sent: Friday, January 11, 2002 8:32 PM
Subject: Re: like transitive closure, but not exactly

> The problem, as you state it, is less than trivial. For each edge
> (u,v), remove u, and do a BFS from v. For all vertices s that are
> reached by the BFS, output ((u,v),s).
>
> Time taken = O((|V|+|E|)*|E|)