marrow/package/tarjan.py
def strongly_connected_components(graph: Graph) -> List:
	"""Find the strongly connected components in a graph using Tarjan's algorithm.
	
	The `graph` argument should be a dictionary mapping node names to sequences of successor nodes.
	"""
	
	assert check_argument_types()
	
	result = []
	stack = []
	low = {}
	
	def visit(node: str):
		if node in low: return
		
		num = len(low)
		low[node] = num
		stack_pos = len(stack)
		stack.append(node)
		
		for successor in graph[node]:
			visit(successor)
			low[node] = min(low[node], low[successor])
		
		if num == low[node]:
			component = tuple(stack[stack_pos:])
			del stack[stack_pos:]
			
			result.append(component)
			
			for item in component:
				low[item] = len(graph)
	
	for node in graph:
		visit(node)
	
	return result
def strongly_connected_components(graph: Graph) -> List:
	"""Find the strongly connected components in a graph using Tarjan's algorithm.
	
	The `graph` argument should be a dictionary mapping node names to sequences of successor nodes.
	"""
	
	assert check_argument_types()
	
	result = []
	stack = []
	low = {}
	
	def visit(node: str):
		if node in low: return
		
		num = len(low)
		low[node] = num
		stack_pos = len(stack)
		stack.append(node)
		
		for successor in graph[node]:
			visit(successor)
			low[node] = min(low[node], low[successor])
		
		if num == low[node]:
			component = tuple(stack[stack_pos:])
			del stack[stack_pos:]
			
			result.append(component)
			
			for item in component:
				low[item] = len(graph)
	
	for node in graph:
		visit(node)
	
	return result
Find the strongly connected components in a graph using Tarjan's algorithm.
	
	The `graph` argument should be a dictionary mapping node names to sequences of successor nodes.