Instituto Superior Tecnico, Lisbon, Portugal
Analysis and Synthesis of Algorithms
###Date
March , 2014
###Authores
Tarjan's Algorithm is an algorithm in graph theory for finding the strongly connected components of a graph. Although proposed earlier, it can be seen as an improved version of Kosaraju's algorithm, and is comparable in efficiency to the path-based strong component algorithm. Tarjan's Algorithm is named for its discoverer, Robert Tarjan
##Implementation The requested project consisted in receiving a file with the following format:
N S (line 1)
A B (line 2)
...
A B (line S)
Where N was the ammount of nodes, S the number of connections and the following lines defined each connection between the nodes.
and we would need to return 3 values
N - Number of cicles present in the given graph
M - Number of nodes of the biggest cicle
S - Number of cicles semi-closed (no connections to the outside)
Should be fully functional and without bugs but use this at you own risk, this was just a small treasure found between many bits and bytes, the upload is just to prevent its loss.
Yes, we're aware of the 'Tarzan' name :)
MIT