37 votes 37 votes Which of the following is the correct decomposition of the directed graph given below into its strongly connected components? $\left \{ P, Q, R, S \right \}, \left \{ T \right \},\left \{ U \right \}, \left \{ V \right \}$ $\left \{ P,Q, R, S, T, V \right \}, \left \{ U \right \}$ $\left \{ P, Q, S, T, V \right \}, \left \{ R \right \},\left \{ U \right \}$ $\left \{ P, Q, R, S, T, U, V \right \}$ Algorithms gateit-2006 algorithms graph-algorithms normal + – Ishrat Jahan asked Oct 31, 2014 • edited Jun 14, 2019 by Lakshman Bhaiya Ishrat Jahan 11.9k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply smsubham commented Dec 26, 2017 reply Follow Share Useful read https://www.geeksforgeeks.org/strongly-connected-components/ 3 votes 3 votes ankitgupta.1729 commented Mar 23, 2018 reply Follow Share A nice explanation by Prof. Shai Simonson to find the Strongly Connected Component(s)(SCC) in a directed graph.. 8 votes 8 votes sushmita commented Oct 3, 2018 reply Follow Share can someone explain the intuition behind taking vertices in decreasing order of finishing times in kosaraju algo? 0 votes 0 votes Please log in or register to add a comment.
Best answer 46 votes 46 votes 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$. papesh answered Sep 17, 2016 • edited Oct 25, 2017 by kenzou papesh comment Share Follow See all 12 Comments See all 12 12 Comments reply Show 9 previous comments manikantsharma commented Sep 3, 2022 reply Follow Share i have few doubts, 1. question is not asking for maximal SCC then why option A and C false. 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 votes 0 votes Dipan Mandal commented Sep 15, 2022 reply Follow Share 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 votes 0 votes Abhrajyoti00 commented Dec 12, 2022 reply Follow Share @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 votes 0 votes Please log in or register to add a comment.
7 votes 7 votes ....... Hira Thakur answered Oct 22, 2017 Hira Thakur comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes ans (B).. Vicky Bajoria answered Jan 14, 2015 Vicky Bajoria comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments srestha commented Jun 23, 2019 reply Follow Share Even without any algo, I am getting B) as answer. 0 votes 0 votes Hirak commented Jun 23, 2019 reply Follow Share @srestha https://youtu.be/RpgcYiky7uw this video is good 0 votes 0 votes srestha commented Jun 23, 2019 reply Follow Share @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 votes 2 votes Please log in or register to add a comment.
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. varunrajarathnam answered Aug 6, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.