DaniWeb IT Discussion Community - Directed Graph Problem

DaniWeb IT Discussion Community (http://www.daniweb.com/forums/index.php)

- Computer Science (http://www.daniweb.com/forums/forum14.html)

- - Directed Graph Problem (http://www.daniweb.com/forums/thread24047.html)

li_xia_er

May 22nd, 2005 6:40 pm

Directed Graph Problem

What I want to achive is when given a directed graph, find out if there is one node that can reach every other node and if there is one node that can be reached by every other. Time complexity should be O(n+m).

I'm into finding all strongly connected parts in the graph and then check the connectivity among those. Can that be an appropriate solution or do I have to rethink it all? Maybe you guys have a better solution.

server_crash

May 23rd, 2005 7:36 am

Re: Directed Graph Problem

Sounds like a spanning tree problem. I think you invert the direction and go from there, or something like that.

All times are GMT -4. The time now is 10:21 pm.