CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
Ahmad
Ahmad

Reputation: 9678

How many strongly connected components is there in this graph?

Consider the following graph. I can distinguish 4 strongly connected components, but they are 5. Which one I missed? Also, can a node be shared in several components?

enter image description here

Upvotes: 1

Views: 253

Answers (1)

sbeliakov
sbeliakov

Reputation: 2199

The 5 components are:

  • Top left node
  • Top right node
  • Bottom left node
  • Bottom right node
  • The rest of the nodes

What you thought of as components are not actually components, because they all can be expanded up to the 5th component from the list.

Notice that it is not possible to extend the listed components, because each of corner nodes is either unreachable from anywhere else (has only outgoing edges) or can't reach any other node (has only incoming edges). Therefore you can't add those corners to bigger component, and can't add anything to corner nodes to make them larger components.

By definition strongly connected components are largest possible (so that it's not possible to further extend them), but there's nothing about not having intersections with each other in definition. However it is easy to show that components defined that way can't have intersections.

Upvotes: 2

Related Questions