The above code gave me `TLE` so, with few minor changes it will work for you. To optimize the given code, you can make a few changes to improve its efficiency: 1. Pass the `adj` vector as a reference to the `dfs` function: Currently, the `adj` vector is passed by value, which creates a copy of the vector in each recursive call. Instead, pass it by reference to avoid unnecessary copies. 2. Use a vector of vectors (`adjT`) instead of an array of vectors for the transpose graph: Declaring `vector adjT[V]` as a variable-length array may cause a stack overflow for large values of `V`. Instead, use a vector of vectors to represent the transpose graph (`adjT`). 3. Reserve memory for the transpose graph vectors: Before pushing elements into `adjT`, reserve memory for each vector based on the size of the corresponding adjacency list in the original graph. This avoids frequent reallocations and improves performance. 4. Use vectors instead of stacks: Instead of using a stack to store the finish times of the nodes in the first DFS, you can use a vector and append nodes at the end. This eliminates the need for reversing the stack later on. Here's the optimized code with these changes: Code : class Solution { private: void dfs(int node, vector& adj, vector& vis, vector& finishOrder) { vis[node] = 1; for (int it : adj[node]) { if (!vis[it]) { dfs(it, adj, vis, finishOrder); } } finishOrder.push_back(node); } void dfs2(int node, vector& adj, vector& vis) { vis[node] = 1; for (int it : adj[node]) { if (!vis[it]) { dfs2(it, adj, vis); } } } public: // Function to find the number of strongly connected components in the graph. int kosaraju(int V, vector& adj) { vector vis(V, 0); vector finishOrder; for (int i = 0; i < V; i++) { if (!vis[i]) { dfs(i, adj, vis, finishOrder); } } // Creating the transpose graph (adjT) vector adjT(V); for (int i = 0; i < V; i++) { vis[i] = 0; for (int it : adj[i]) { adjT[it].push_back(i); } } // Last DFS using the finish order int scc = 0; for (int i = V - 1; i >= 0; i--) { int node = finishOrder[i]; if (!vis[node]) { scc++; dfs2(node, adjT, vis); } } return scc; } }; These optimizations should improve the efficiency of the code.
I think after seeing the video if you read the striver sheet explanation for the same question it will give you more insight since it is really well written. I really liked it!
the first step is same as topo sort using dfs technique, will not work with bfs (khann's algo) due to directed cyclic graphs.but if you apply topo sort using dfs in directed cyclic graphs ,it will work.
@@takeUforward when we sort all the edges according to finishing time and store it in stack like this 0,1,2,3,4,5,6,7 , so instead of storing in stack can we use queue and then when we pop out elements from queue we start DFS from 7 instead of 0 and 7 is not connected to anyone so we found 1st SCC then we pop 6 and do DFS and found 2nd SCC then we pop 3 and do DFS and got 3rd SCC and so on. In this approach we don't need to reverse the graph. Can we do like this?
We can use the same dfs again by passing a dummy stack: public void dfs(ArrayList adj, int[] vis, Stack st, int node){ vis[node] = 1; for(int it : adj.get(node)){ if(vis[it] == 0){ dfs(adj, vis, st, it); } } st.push(node); } //Function to find number of strongly connected components in the graph. public int kosaraju(int V, ArrayList adj) { int[] vis = new int[V]; Stack st = new Stack(); for(int i = 0; i < V; i++){ if(vis[i] == 0){ dfs(adj, vis, st, i); } } ArrayList adjT = new ArrayList(); for(int i = 0; i < V; i++) adjT.add(new ArrayList()); for(int i = 0; i < V; i++){ vis[i] = 0; for(int it : adj.get(i)){ // previously: i -> it // Now make it: i i adjT.get(it).add(i); } } int scc = 0; while(!st.isEmpty()){ int node = st.pop(); if(vis[node] == 0){ scc++; dfs(adjT, vis, new Stack(), node); } } return scc; }
@@DheerajDivaker Yes you are right but here since graph can be cyclic as well as acyclic , so incase of CYCLIC one edge which is causing cycle is not stored , like 1->2->3->1 , is only stored as [ 1, 2 ,3 ] . So ultimately we should not call it as a toposort ,but implementation is exactly same.
guys just in case any one wondering why that stack of dfs calls was required that is only if u r solving for the second case of actually printing the components and not just finding number of components. like based on the stack trace u can make a note of elements while popping and put them into groups and print
Note: we can't say this as a Topological sort(as topological sort using DFS will get you stuck in Loop i.e cycle), but its a bit different. Its topological Sort for the SCC.
This code is giving tle in gfg, the below code is same as what you thought class Solution { private: void dfs(int node, vector &vis,vector adj,stack &st) { vis[node]=1; for(auto it: adj[node]) { if(vis[it]==0) { dfs(it,vis,adj,st); } } st.push(node); }
void dfs1(int node, vector &vis, vector adjT[]) { vis[node]=1; for(auto it: adjT[node]) { if(vis[it]==0) { dfs1(it,vis,adjT); } } } public: //Function to find number of strongly connected components in the graph. int kosaraju(int V, vector& adj) { //code here vector vis(V,0); stack st; for(int i=0;i
When we are finding out the time complexity of any algorithm, why isn't the lower bound also considered?? Ideally speaking for the method of dfs, the time complexity is theta(V + E). So the time complexity of SCC must also be theta(V + E).
HEY STRIVER, We can also reduce the time and steps if first getting there there finishing time and store in a queue rather then stack so because of FIFO we know first element to finish so we don't need to reverse the graph either we can directly go through the finishing elements which are already reverse with respect to graph it will reduce steps and clean code too. correct me if I m wrong
we can't .try dryrun on 1st example , suppose u created vector which store the timing then timing will be {1 2 4 3 0} if you try dfs accoording to this you still cannot find scc.
Sorting makes you sure that you process those nodes first which lie at the end of a directed path. If you apply it randomly, you might start dfs from the start node or any node in the middle and will visit the nodes that are not a part of the SCC as well.
@@rahulsangvikar7973 but we already reversed the nodes and its not connected anymore ,,,also we have visited array so we can ignore already processed node
Why sorting is needed. Can't be simply reverse the edges and then do dfs on all the nodes. We can get group of nodes which are there in cycle which is ultimately our strongly connected components.
By doing that you've completely ignored the "Finish time" concept. While doing the dfs in the transpose graph( with reverse edges) you should start with the component which does not have an edge going to the other scc.. that's why we use a stack and pop the top most element to perform dfs. If u want, I'll post my python code
In given example if we just make a little change with 3->2 then after reversing the edge will be 2->3 so in step 3 dfs call 2 will also go to 3 . I feel like it should not go to 3
@striver... is there really a need to reverse the graph...or the edges... After finding the finishing times and storing them....we could start dfs with the ascending order of finishing time....that would give us the 7th node first...then 6th....then 3rd and then 2nd..... this would give us 4 SCC and also the SCC ....may be just in a different order but still SCC
How do I pick the starting node for sorting. In the above example if we would have started sorting from Node 3, I would have never reached 0, 1, 2. So how to calculate this increasing time for all nodes efficiently.
Can we skip the step 1, and just reverse all the edges ? Because after reversing edges, components will be logically separated and we can run DFS on it separately, and can find the nodes in each component. Please can anyone guide me on this ?
for eg, in the same example as striver's, if you reverse the edge between 2 & 3, with your process, when the graph is reversed, the dfs(0) has 3 as well in it, this is the loop hole. Whereas, in the algo, when we do dfs first and calculate finishing times, we get 3 at the top of the stack, so now we can make different dfs calls for each scc. Hope you understand. Have a great day!
@@Jinxed192 the edge is like 0->1, 1->2 , 2->0 , 2->3 then how you are saying reversing the edges between 2->3 will be inside the dis(0)..And what Aditya is commenting is totally fine.
The problem with graphs: The algos are easy code is easy dry run is easy chill But almost everytime this ques isnt answered Why this algo works like the basis of working of algorithms> Moreover this all is so volatile I'll forget this like in what 3 days>?
The difference lies in the absence of a cycle in the original example, as per the definition of topological sorting. This implies that we should first check for cycles before attempting to find a topological sort. In the provided example, however, we are generating an order where nodes are arranged based on the time they were visited. This is facilitated by the algorithm's flow, which uses a visited array ensuring that each node is visited exactly once. If a cycle were detected during traversal, the algorithm would indicate this by returning false, signifying that a valid topological sort does not exist. In this context, the primary purpose is to populate the stack for subsequent manipulations and operations, rather than solely ensuring a strict topological order.
Understanding this algorithm can be quite complex because it isn't solely reliant on the direction of traversal or the starting node for the initial DFS. Additionally, it doesn't guarantee visiting all nodes in a single DFS pass. The crucial aspect is how the algorithm manages to account for these complexities using the stack, even after performing edge reversals. The algorithm's sophistication lies in its ability to handle these scenarios by utilizing the stack effectively, ensuring that it accommodates inversions regardless of traversal direction or initial starting conditions.
For example, let's consider SCC1, SCC2, SCC3, SCC4, SCC5. Suppose node 0 is in SCC3, and SCC3 leads to SCC4, and SCC4 leads to SCC5. However, SCC2 leads to SCC3, and SCC1 leads to SCC2. So, you start DFS from SCC3 and visit SCC4 and SCC5 in the first traversal. The stack will store them. During the initial DFS traversal, the backtrack keeps track of the order of elements in that stack and fills them in an order based on finishing time. Now, SCC2 and SCC1 are still unvisited, but here's the interesting part: in the next steps of DFS traversal, even though DFS is called for them later, they will finish before 0 in terms of finishing time. This is because the DFS for SCC2 and SCC1 starts after the DFS for 0 ends completely. Kosaraju ingeniously used iteration with backtracking to manage this complex traversal. When DFS is called to calculate SCC2 (the third step in the example), this time, since we have reversed the edges, DFS would not go to SCC3 as it normally would, because SCC3 couldn't reach SCC2 in the original direction (this aspect demonstrates the algorithm's elegance). Therefore, recursion and iteration work together seamlessly to make this algorithm effective.
19:55 Why did you mention to write as private function. Is there any advantage of it over public. As I tested in run time and got public working faster than private. Also from outer source noone is calling that dfs function. So kindly elaborate please
Undeniably the best teaching methodology and the content for strengthening DSA
Your videos and the SDE sheet are helping me so much to brush up the DSA concepts and learn the ones I ignored in college. A BIG THANK YOU!!
The above code gave me `TLE`
so, with few minor changes it will work for you.
To optimize the given code, you can make a few changes to improve its efficiency:
1. Pass the `adj` vector as a reference to the `dfs` function: Currently, the `adj` vector is passed by value, which creates a copy of the vector in each recursive call. Instead, pass it by reference to avoid unnecessary copies.
2. Use a vector of vectors (`adjT`) instead of an array of vectors for the transpose graph: Declaring `vector adjT[V]` as a variable-length array may cause a stack overflow for large values of `V`. Instead, use a vector of vectors to represent the transpose graph (`adjT`).
3. Reserve memory for the transpose graph vectors: Before pushing elements into `adjT`, reserve memory for each vector based on the size of the corresponding adjacency list in the original graph. This avoids frequent reallocations and improves performance.
4. Use vectors instead of stacks: Instead of using a stack to store the finish times of the nodes in the first DFS, you can use a vector and append nodes at the end. This eliminates the need for reversing the stack later on.
Here's the optimized code with these changes:
Code :
class Solution {
private:
void dfs(int node, vector& adj, vector& vis, vector& finishOrder) {
vis[node] = 1;
for (int it : adj[node]) {
if (!vis[it]) {
dfs(it, adj, vis, finishOrder);
}
}
finishOrder.push_back(node);
}
void dfs2(int node, vector& adj, vector& vis) {
vis[node] = 1;
for (int it : adj[node]) {
if (!vis[it]) {
dfs2(it, adj, vis);
}
}
}
public:
// Function to find the number of strongly connected components in the graph.
int kosaraju(int V, vector& adj) {
vector vis(V, 0);
vector finishOrder;
for (int i = 0; i < V; i++) {
if (!vis[i]) {
dfs(i, adj, vis, finishOrder);
}
}
// Creating the transpose graph (adjT)
vector adjT(V);
for (int i = 0; i < V; i++) {
vis[i] = 0;
for (int it : adj[i]) {
adjT[it].push_back(i);
}
}
// Last DFS using the finish order
int scc = 0;
for (int i = V - 1; i >= 0; i--) {
int node = finishOrder[i];
if (!vis[node]) {
scc++;
dfs2(node, adjT, vis);
}
}
return scc;
}
};
These optimizations should improve the efficiency of the code.
Thanks a lot man!!
yeah that improves the code a lot!
Thank you so much
Your explanation goes straight inn , such a brilliant teacher!!
I think after seeing the video if you read the striver sheet explanation for the same question it will give you more insight since it is really well written. I really liked it!
Can you provide me link of that..
It is in the description
I thought I was done with graphs 😅
Literally me too...😅
@@SomeshCodes me too
Honestly, this playlist deserves Millions views and comments..... Thanks for all you do Striver!!!
Brilliant explanation! Thanks for the graph series, the best teacher ever!
the first step is same as topo sort using dfs technique, will not work with bfs (khann's algo) due to directed cyclic graphs.but if you apply topo sort using dfs in directed cyclic graphs ,it will work.
This is much intutive than the previous video on kosaraju(other graph playlist)
Yes I read the comments, and then made this one.
@@takeUforward you have changed the lives of so many students, you have blessings of many. ♥️
@@takeUforward when we sort all the edges according to finishing time and store it in stack like this 0,1,2,3,4,5,6,7 , so instead of storing in stack can we use queue and then when we pop out elements from queue we start DFS from 7 instead of 0 and 7 is not connected to anyone so we found 1st SCC then we pop 6 and do DFS and found 2nd SCC then we pop 3 and do DFS and got 3rd SCC and so on. In this approach we don't need to reverse the graph. Can we do like this?
@@tanmaypal2003 Nice observation. I think this should work fine.
@@tanmaypal2003 yes
And here comes the real OG Striver.❤
Understood!! Thank you for this amazing explanation.
Finally understood kosaraju algo. Thank you striver.
you are really good man!!! appreciate ur clarity of thoughts and words!! kudos and best wishes!!🎉
thanks for the clear explanation of this complicated topic
Just amazing.
Great Explanation.
Understood! Super excellent explanation as always, thank you very much!!
Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Going to end the graph..❤ understood
mazaaaaaaa aaaaaaaagyaaaaaaaaaaa
this is first time i have come across any of your videos
der aaye par durust aaye....
let me subscribe!
Excellent tutorial and really helpful, thanks!!
Just realised one thing. You can avoid reversing the graph if you were to put the time in a queue instead of a stack.
No you need stack cause if you use Queue it will keep going on to next SSC using the visited araay
exactly my thought
My Last graph question for this series 😊
class Solution
{
private:
void dfs(int node,vectoradj[],vector&vis,stack&st) // dfs for adj
{
vis[node]=1;
for(auto it:adj[node])
{
if(vis[it]==0)
{
dfs(it,adj,vis,st);
}
}
st.push(node);
}
void dfs2(int node,vectoradjT[],vector&vis) // dfs for adjT
{
vis[node]=1;
for(auto it:adjT[node])
{
if(vis[it]==0)
{
dfs2(it,adjT,vis);
}
}
}
public:
//Function to find number of strongly connected components in the graph.
int kosaraju(int V, vector adj[])
{
vectorvis(V,0);
stackst;
vector adjT[V]; // adj list after reversing edges
for(int i=0;i
You are a very good teacher apse sikhna easy lagta hai
We can use the same dfs again by passing a dummy stack:
public void dfs(ArrayList adj, int[] vis, Stack st, int node){
vis[node] = 1;
for(int it : adj.get(node)){
if(vis[it] == 0){
dfs(adj, vis, st, it);
}
}
st.push(node);
}
//Function to find number of strongly connected components in the graph.
public int kosaraju(int V, ArrayList adj)
{
int[] vis = new int[V];
Stack st = new Stack();
for(int i = 0; i < V; i++){
if(vis[i] == 0){
dfs(adj, vis, st, i);
}
}
ArrayList adjT = new ArrayList();
for(int i = 0; i < V; i++) adjT.add(new ArrayList());
for(int i = 0; i < V; i++){
vis[i] = 0;
for(int it : adj.get(i)){
// previously: i -> it
// Now make it: i i
adjT.get(it).add(i);
}
}
int scc = 0;
while(!st.isEmpty()){
int node = st.pop();
if(vis[node] == 0){
scc++;
dfs(adjT, vis, new Stack(), node);
}
}
return scc;
}
sorting according to finish time can be done using toposort:)
that is toposort only. Toposort can be done using stack and that's what it is here.
@abcsumit Toposort banega hi nahi, wo sirf DAG mein work karta hai.
@@deviprasad_bal Toposort banega hi nahi, wo sirf DAG mein work karta hai.
@@DheerajDivaker Yes you are right but here since graph can be cyclic as well as acyclic , so incase of CYCLIC one edge which is causing cycle is not stored , like 1->2->3->1 , is only stored as [ 1, 2 ,3 ] .
So ultimately we should not call it as a toposort ,but implementation is exactly same.
@@Anonymous_Coder yes absolutely correct.
understood, nice explanation
Man Striver ur incredible
guys just in case any one wondering why that stack of dfs calls was required that is only if u r solving for the second case of actually printing the components and not just finding number of components.
like based on the stack trace u can make a note of elements while popping and put them into groups and print
without using stack, how to do solve the first case of finding no. of compo? I mean to find no. of components also we need it in sorted way right?
@@vishalcheeti8374 we already reversed the graph so it will count the component for every dfs call,but somehow without stack its not working
Note: we can't say this as a Topological sort(as topological sort using DFS will get you stuck in Loop i.e cycle), but its a bit different. Its topological Sort for the SCC.
Man, amazing explaination. Hats off to you buddy
Understood after a little bit of effort.
Long time no see sir 😊
Thank you for posting 🥰🔥💖
Thanks for Explaining the logic
You explain so well ❤❤
Thank you sir 🙏
great work sir i just watch ur few video and ur content is awesome
maza aaala re ala striver aala
GFG compiler giving TLE, don't know why?? :(
Thanks for Explaining this concept :) really liked your explaination
This code is giving tle in gfg, the below code is same as what you thought
class Solution
{
private:
void dfs(int node, vector &vis,vector adj,stack &st)
{
vis[node]=1;
for(auto it: adj[node])
{
if(vis[it]==0)
{
dfs(it,vis,adj,st);
}
}
st.push(node);
}
void dfs1(int node, vector &vis, vector adjT[])
{
vis[node]=1;
for(auto it: adjT[node])
{
if(vis[it]==0)
{
dfs1(it,vis,adjT);
}
}
}
public:
//Function to find number of strongly connected components in the graph.
int kosaraju(int V, vector& adj)
{
//code here
vector vis(V,0);
stack st;
for(int i=0;i
To resolve this issue, make sure that adjT is declared as a vector of vectors
vectoradjT(V);
thank you very muchhh! You've literally changed so many lives ✌️
awesome explanation!
Awesome work 👏
When we are finding out the time complexity of any algorithm, why isn't the lower bound also considered??
Ideally speaking for the method of dfs, the time complexity is theta(V + E).
So the time complexity of SCC must also be theta(V + E).
Amazing content🔥
HEY STRIVER, We can also reduce the time and steps if first getting there there finishing time and store in a queue rather then stack so because of FIFO we know first element to finish so we don't need to reverse the graph either we can directly go through the finishing elements which are already reverse with respect to graph it will reduce steps and clean code too.
correct me if I m wrong
yes you are wrong. on so many levels that it cant be fixed anymore.
Understood Sir!
Big fan of your work striver
Why is it important to reverse the edges, can't we just start the dfs in reverse order ?
Like in the example start from 7
can any1 please explain
we can't .try dryrun on 1st example ,
suppose u created vector which store the timing then timing will be
{1 2 4 3 0} if you try dfs accoording to this you still cannot find scc.
Yes, you can do that. But, this video is about Kosaraju's algorithm, which is implemented this way.
amazing content!
Understood, thanks!
UNDERSTOOD
Understood brother. Could you please upload videos on sliding window and 2 pointers?? I saw most amazon OA will be based on that only.
Already there in the channel bro
Understood 👍
why we need to sort, why can't we simply use ?
for(int i=0;i
same question
Sorting makes you sure that you process those nodes first which lie at the end of a directed path. If you apply it randomly, you might start dfs from the start node or any node in the middle and will visit the nodes that are not a part of the SCC as well.
@@rahulsangvikar7973 but we already reversed the nodes and its not connected anymore ,,,also we have visited array so we can ignore already processed node
🔥🔥🔥🔥
Explanation
Understood.
Why sorting is needed. Can't be simply reverse the edges and then do dfs on all the nodes. We can get group of nodes which are there in cycle which is ultimately our strongly connected components.
By doing that you've completely ignored the "Finish time" concept. While doing the dfs in the transpose graph( with reverse edges) you should start with the component which does not have an edge going to the other scc.. that's why we use a stack and pop the top most element to perform dfs. If u want, I'll post my python code
Please perform a dry run for the first example. Swap nodes 0 and 7, and then complete the dry run.
In given example if we just make a little change with 3->2 then after reversing the edge will be 2->3 so in step 3 dfs call 2 will also go to 3 . I feel like it should not go to 3
i have the same confusion that if we start with 7 in the start rather than 0 , we will get wrong connected components
mast padha dia bahiya
please make videos on Eulerian paths also.
thought process is very tricky
Understooddd!!
@striver... is there really a need to reverse the graph...or the edges...
After finding the finishing times and storing them....we could start dfs with the ascending order of finishing time....that would give us the 7th node first...then 6th....then 3rd and then 2nd..... this would give us 4 SCC and also the SCC ....may be just in a different order but still SCC
Understood❤
understood
amazing content
Understood!
reach++
Loved it
Understood!!
Sir is sorting edges according to finishing time same as topological sort?
Will topological sort work in cyclic graphs?
Awesome thanks a lot
Understood
If you don't understand in one go just watch the video in 1x you will get better understanding slowly
understooood
crystal clear
awsm explanation thank u so much
Thanks buddy
thanks for the video
understood sir
A single dfs will work by using flag(fillStack) parameter....
Hey
class Solution
{
private:
void dfs(int node, vector &vis, vector adj,
stack &st) {
vis[node] = 1;
for (auto it : adj[node]) {
if (!vis[it]) {
dfs(it, vis, adj, st);
}
}
st.push(node);
}
private:
void dfs3(int node, vector &vis, vector adjT) {
vis[node] = 1;
for (auto it : adjT[node]) {
if (!vis[it]) {
dfs3(it, vis, adjT);
}
}
}
public:
int kosaraju(int V, vector& adj)
{
vector vis(V, 0);
stack st;
for (int i = 0; i < V; i++) {
if (!vis[i]) {
dfs(i, vis, adj, st);
}
}
vector adjT(V);
for (int i = 0; i < V; i++) {
vis[i] = 0;
for (auto it : adj[i]) {
// i -> it
// it -> i
adjT[it].push_back(i);
}
}
int scc = 0;
while (!st.empty()) {
int node = st.top();
st.pop();
if (!vis[node]) {
scc++;
dfs3(node, vis, adjT);
}
}
return scc;
}
};
This same code giving TLE on GFG
I guess they updated the time limit thingy
How do I pick the starting node for sorting.
In the above example if we would have started sorting from Node 3, I would have never reached 0, 1, 2. So how to calculate this increasing time for all nodes efficiently.
whats the problem in doing only reversing thr edges and dfs. why store them in first?
amazing..
Thanks🙌
Isn't the first step same as topological sort?
Yes Bro its the same
Can we skip the step 1, and just reverse all the edges ? Because after reversing edges, components will be logically separated and we can run DFS on it separately, and can find the nodes in each component.
Please can anyone guide me on this ?
Ohh, got it. It's for the efficiency
for eg, in the same example as striver's, if you reverse the edge between 2 & 3, with your process, when the graph is reversed, the dfs(0) has 3 as well in it, this is the loop hole. Whereas, in the algo, when we do dfs first and calculate finishing times, we get 3 at the top of the stack, so now we can make different dfs calls for each scc. Hope you understand. Have a great day!
@@Jinxed192 Thanks for explaination.
That means we must know from where to start, to void futher conflicts.
@@Jinxed192 the edge is like 0->1, 1->2 , 2->0 , 2->3 then how you are saying reversing the edges between 2->3 will be inside the dis(0)..And what Aditya is commenting is totally fine.
The problem with graphs:
The algos are easy code is easy dry run is easy chill
But almost everytime this ques isnt answered Why this algo works like the basis of working of algorithms>
Moreover this all is so volatile I'll forget this like in what 3 days>?
understood 🥶
is first step similiar to topo sort?
Isnt that stack thing, is topological sort ?
The difference lies in the absence of a cycle in the original example, as per the definition of topological sorting. This implies that we should first check for cycles before attempting to find a topological sort. In the provided example, however, we are generating an order where nodes are arranged based on the time they were visited. This is facilitated by the algorithm's flow, which uses a visited array ensuring that each node is visited exactly once. If a cycle were detected during traversal, the algorithm would indicate this by returning false, signifying that a valid topological sort does not exist. In this context, the primary purpose is to populate the stack for subsequent manipulations and operations, rather than solely ensuring a strict topological order.
Understanding this algorithm can be quite complex because it isn't solely reliant on the direction of traversal or the starting node for the initial DFS. Additionally, it doesn't guarantee visiting all nodes in a single DFS pass. The crucial aspect is how the algorithm manages to account for these complexities using the stack, even after performing edge reversals.
The algorithm's sophistication lies in its ability to handle these scenarios by utilizing the stack effectively, ensuring that it accommodates inversions regardless of traversal direction or initial starting conditions.
For example, let's consider SCC1, SCC2, SCC3, SCC4, SCC5. Suppose node 0 is in SCC3, and SCC3 leads to SCC4, and SCC4 leads to SCC5. However, SCC2 leads to SCC3, and SCC1 leads to SCC2.
So, you start DFS from SCC3 and visit SCC4 and SCC5 in the first traversal. The stack will store them. During the initial DFS traversal, the backtrack keeps track of the order of elements in that stack and fills them in an order based on finishing time.
Now, SCC2 and SCC1 are still unvisited, but here's the interesting part: in the next steps of DFS traversal, even though DFS is called for them later, they will finish before 0 in terms of finishing time. This is because the DFS for SCC2 and SCC1 starts after the DFS for 0 ends completely. Kosaraju ingeniously used iteration with backtracking to manage this complex traversal.
When DFS is called to calculate SCC2 (the third step in the example), this time, since we have reversed the edges, DFS would not go to SCC3 as it normally would, because SCC3 couldn't reach SCC2 in the original direction (this aspect demonstrates the algorithm's elegance).
Therefore, recursion and iteration work together seamlessly to make this algorithm effective.
Imo , the best graph algorithm.
@@hardikjuneja1 Thank you for detailed explanation bro 😃
Is there any relation in this algo and topo sort as we get reverse topo from stack
Can't we use queue and then not reversing the edges and just count no of scc of back, but it's not working idk
edges ko reverse karne se SCCs separate ho rahe hai..
bhaiya can,t we solve it by reversing the stack instead of reversing the graph
stack reversal will reverse the finish time but reversing the graph does not allow us to go from one scc to another scc
19:55 Why did you mention to write as private function. Is there any advantage of it over public. As I tested in run time and got public working faster than private. Also from outer source noone is calling that dfs function. So kindly elaborate please
understood💛💙💛
choit💥💥💥