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.7k 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 Puja Mishra commented Jan 28, 2017 reply Follow Share i am getting A ... by applying kosaraju's algorithm .... –5 votes –5 votes akash.dinkar12 commented Jul 16, 2017 reply Follow Share @ puja How??? 0 votes 0 votes Puja Mishra commented Jul 18, 2017 reply Follow Share I hav said it in answer ..... 0 votes 0 votes sushmita commented Aug 30, 2017 reply Follow Share kosaraju's algorithm is clearly giving B as answer. 3 votes 3 votes sushmita commented Aug 31, 2017 reply Follow Share fine downvote it.. but it wont change the fact.... @ downvoter. 5 votes 5 votes rishi71662data4 commented Oct 22, 2017 reply Follow Share Kosaraju's algorithm gives B as answer. Why downvote on the above answer ? 0 votes 0 votes Ayush Upadhyaya commented Dec 18, 2017 reply Follow Share Kosaraju's algorithm steps executed. 12 votes 12 votes Kuljeet Shan commented Mar 10, 2019 reply Follow Share Clear the concepts ! Take a look. https://youtu.be/5wFyZJ8yH9Q 10 votes 10 votes ajatinsohlot commented Aug 7, 2021 reply Follow Share KOSARAJU’S ALGO: Compute DFS(G) with finishing timing of each vertex Construct transpose of graph G Call DFS on transpose with decreasing ordering of finishing time Resulting trees will be strongly connected components 4 votes 4 votes 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.