in Algorithms edited by
9,093 views
36 votes
36 votes

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 \}$ 
in Algorithms edited by
9.1k views

3 Comments

3
3

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

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

6 Answers

44 votes
44 votes
Best answer

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

edited by

4 Comments

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

@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

0
0
7 votes
7 votes

.......

3 votes
3 votes
ans (B)..

4 Comments

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

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

2
2
2 votes
2 votes
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.
Answer:

Related questions