Re: strongly connected graph

From: Sebi (harko_at_cluj.astral.ro)
Date: 12/30/03 

Date: 30 Dec 2003 00:49:35 -0800

Pento <robby.goetschalckx@student.kuleuven.ac.be.NOSPAM> wrote in message news:<Xns9460C99E9E74Frobbygoetschalckxstu@134.58.127.12>...
> harko@cluj.astral.ro (Sebi) wrote in
> news:2cf84663.0312290748.6f10fde@posting.google.com:
>
> > I came up with this idea that seems correct (but it has good chances
> > of being a bogus idea because it seems to easy ): keep in a set the
> > in-degrees of each vertex and in the other set the out-degrees of each
> > vertex.if the two sets are identical(after sorting them) it means that
> > the graph is strongly connected.
>
> I don't think that's correct.
>
> Consider the following graph :
>
> a -> b
> b -> a
>
> c -> d
> d -> c
>
> It is not strongly connected, but all nodes have the same in-degree as out-
> degree.

yep
but what about the graph where between every two nodes there is no more than one
edge? (e.g if a->b then b cant ->a)