Member Avatar for li_xia_er

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.

  • 2 Contributors
  • 1 Reply
  • 121 Views
  • 18 Hours Discussion Span
  • Latest Post Latest Post by server_crash
Member Avatar for server_crash

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.