GATE IT 2006 | Question: 46

Question

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

• A. $\left \{ P, Q, R, S \right \}, \left \{  T \right \},\left \{  U \right \}, \left \{  V \right \}$
• B. $\left \{ P,Q, R, S, T, V \right \}, \left \{  U  \right \}$ 
• C. $\left \{ P, Q, S, T, V \right \}, \left \{  R \right \},\left \{  U \right \}$ 
• D. $\left \{ P, Q, R, S, T, U, V \right \}$ 

Comments

Useful read

https://www.geeksforgeeks.org/strongly-connected-components/

---

A nice explanation by Prof. Shai Simonson to find the Strongly Connected Component(s)(SCC) in a directed graph..

---

can someone explain the intuition behind taking vertices in decreasing order of finishing times in kosaraju algo?

Answer 1

Here the answer is B.

A graph is said to be strongly connected if every vertex is reachable from every other vertex.

The strongly connected component is always maximal that is if $x$ is strongly connected component there should not exist another strongly connected component which contains $x$.

If we take $R$ as a strongly connected component but which is part of $PQRS$ and $PQRS$ is part of $PQRSVT$.

Comments

i have few doubts,

1. question is not asking for maximal SCC  then why option A and C false.

2. can we say that if a SCC with 6 vertices possible then no component with same set of vertices (but less than 6) will be SCC. Example: PQRSTV is SCC but so is PQRS, then why A and C is not correct

---

SCCs are always formed in such a way that they are maximal. So you always take the largest set of nodes that are strongly connected.

---

@manikantsharma 

1. Read it once again :-

The strongly connected component is always maximal that is if x is strongly connected component there should not exist another strongly connected component which contains x.

2. NO we can't

Answer 2

.......

Answer 3

ans (B)..

Comments

Even without any algo, I am getting B) as answer.

---

@srestha

https://youtu.be/RpgcYiky7uw

this video is good

---

@Hirak

That is ok.

But why do we need it here? It takes lots of time. So, I think with the definition of strongly connected component, we can say B) is answer. isn't it?

See the definition of strongly connected component. It tells , if we go from one vertex of the graph to all other vertex then the graph is strongly connected. Now chk here, only option B) match. Isn't it?

Answer 4

In a strongly connected component every two vertices must be reachable from one to other and it is maximal component.
From given graph {P, Q, R, S, T, V} and {U} are strongly connected components.