can be done in O(n^2) also
below is a rough pseudocode
initialize visited[v]=0
for every vertex v{
call dfs(v)
check if al visited are 1 or not
if all visited break;
else do visited[v]=0 again.
}
correcf me if i'm missing anything
On Fri, Jul 16, 2010 at 5:38 AM, Gene <[email protected]> wrote:
> Construct the transitive closure of the graph. You can use Warshall's
> algorithm, which is O(v^3) in run time. If any row of the adjacency
> matrix is all 1's, the corresponding vertex can reach all others. You
> can ignore the diagonal element if you don't care whether vertices are
> reachable from themselves (i.e. whether they are contained in a
> cycle).
>
> On Jul 12, 1:06 pm, Love-143 <[email protected]> wrote:
> > 1.Give an efficient algorithm which takes as input a directed graph G =
> > (V,E), and determines whether or not there is a vertex s is in V from
> which
> > all other vertices are reachable.?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
