Strongly connected component

Question

Find the no of strongly connected components for the below graph.

• A. $5$
• B. $4$
• C. $9$
• D. $2$

Comments

yep, 4 strongly connected components:

{A, B ,E} {F,G} {C,D} {H}

strongly connected component: there is a path between each pair of vertices and no sub-component is strongly connected component.

---

@Manu Thakur Sir, According to diagram given in Wikipedia, Component {CDH} and its subcomponent are {cd} and {dh} and both are connected, and they took CDH as one connected component, which is contradicting:-

no sub-component is strongly connected component.

Ref :- https://en.wikipedia.org/wiki/Strongly_connected_component 

---

Shubhanshu we take maximal strongly connected component, for example, take CDH, C, D and H are separately connected components as each isolated vertex is a connected graph, but still we took CDH because CDH is maximally strongly connected component

---

But sir, its subcomponent i.e. CD and DH are also strongly connected and according to your definition "no sub-component is the strongly connected component." But here, its subcomponent are also strongly connected.

---

Shubhanshu, i meant to say, if we have taken a component as strongly connected, then its any sub-component should not be in our list.
if we have taken CDH as strongly connected component then either CD or DH is not strongly component component. yes, that is correct, that CD are strongly connected but CD is not strongly connected component as it's not maximal.

---

In simple language, find the possible maximum number of strongly connected vertices and put them into one group.

---

Like we are looking for maximum grouping in K-map. ryt?

---

yes.

Answer 1

The strongly connected components in digraph are- if there is the path from node A to node B and another path from node B to node A. In the question pairs- AB, AE, CD, FG from strong connected components.