9,093 views

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

1. $\left \{ P, Q, R, S \right \}, \left \{ T \right \},\left \{ U \right \}, \left \{ V \right \}$
2. $\left \{ P,Q, R, S, T, V \right \}, \left \{ U \right \}$
3. $\left \{ P, Q, S, T, V \right \}, \left \{ R \right \},\left \{ U \right \}$
4. $\left \{ P, Q, R, S, T, U, V \right \}$

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?

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$.

by

i have few doubts,

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

1. 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.

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

.......

ans (B)..

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

@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?

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.