Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save SuryaPratapK/41adc04cc89a3ffb6e8d2398f6fd2a8d to your computer and use it in GitHub Desktop.
Save SuryaPratapK/41adc04cc89a3ffb6e8d2398f6fd2a8d to your computer and use it in GitHub Desktop.
#include<bits/stdc++.h>
using namespace std;
#define V 7
#define pb push_back
unordered_map<int,vector<int>> adj;
void DFS(int u,vector<int>& disc,vector<int>& low,stack<int>& mystack,vector<bool>& presentInStack)
{
static int time = 0;
disc[u] = low[u] = time;
time+=1;
mystack.push(u);
presentInStack[u] = true;
for(int v: adj[u])
{
if(disc[v]==-1) //If v is not visited
{
DFS(v,disc,low,mystack,presentInStack);
low[u] = min(low[u],low[v]);
}
//Differentiate back-edge and cross-edge
else if(presentInStack[v]) //Back-edge case
low[u] = min(low[u],disc[v]);
}
if(low[u]==disc[u]) //If u is head node of SCC
{
cout<<"SCC is: ";
while(mystack.top()!=u)
{
cout<<mystack.top()<<" ";
presentInStack[mystack.top()] = false;
mystack.pop();
}
cout<<mystack.top()<<"\n";
presentInStack[mystack.top()] = false;
mystack.pop();
}
}
void findSCCs_Tarjan()
{
vector<int> disc(V,-1),low(V,-1);
vector<bool> presentInStack(V,false); //Avoids cross-edge
stack<int> mystack;
for(int i=0;i<V;++i)
if(disc[i]==-1)
DFS(i,disc,low,mystack,presentInStack);
}
int main()
{
adj[0].pb(1);
adj[1].pb(2);
adj[1].pb(3);
adj[3].pb(4);
adj[4].pb(0);
adj[4].pb(5);
adj[4].pb(6);
adj[5].pb(6);
adj[6].pb(5);
findSCCs_Tarjan();
return 0;
}
//TIME COMPLEXITY: O(V+E)
@dev-sanjay
Copy link

dev-sanjay commented Jul 3, 2022

Can anybody help why this code is not working for a specific test case on geeksforgeeks?

  tarjanDfs(graph, vertex, discoveryTime, lowTime, isVertexInStack, stack, components, time, count) {
    	discoveryTime[vertex] = lowTime[vertex] = time++;
    	
    	stack.push(vertex);
    	isVertexInStack[vertex] = true;
    	
    	for(const neighbour of graph[vertex]) {
    		if(discoveryTime[neighbour] == -1) {
    			this.tarjanDfs(graph, neighbour, discoveryTime, lowTime, isVertexInStack, stack, components, time, count);
    			lowTime[vertex] = Math.min(lowTime[vertex], lowTime[neighbour]);
    		} else if(isVertexInStack[neighbour]) {
    			lowTime[vertex] = Math.min(lowTime[vertex], discoveryTime[neighbour]);
    		}
    	}
    
    	// If vertex is the head of the SCC
    	if(lowTime[vertex] == discoveryTime[vertex]) {
    		const scc = [];
            let node = stack.pop();
    
    		while(node != vertex) {
    			scc.push(node);
    			isVertexInStack[node] = false;
    			node = stack.pop();
    		}
    		scc.push(node);
    		isVertexInStack[node] = false;
    		components.push(scc.sort()) ;
    		 
    	}
    }
    
    tarjans(V,adj)
    {
    	const discoveryTime = new Array(V).fill(-1);
    	const lowTime = new Array(V).fill(-1);
    	const isVertexInStack = new Array(V).fill(false);
    	const stack = [];
    	const components = [];
    
    	for(let vertex = 0; vertex < V; vertex++) {
    		if(discoveryTime[vertex] == -1) {
    			this.tarjanDfs(adj, vertex, discoveryTime, lowTime, isVertexInStack, stack, components, 0);
    		}
    	}
        
    	return components.sort((l1, l2) => l1[0] - l2[0]);
    }

@2tanayk
Copy link

2tanayk commented Jul 9, 2022

i too am having the same issue

@chakkraborty
Copy link

top G channel , hands down

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment