Implementation
You are required to implement correctly and efficiently the căutare în depthfirst search algorithm (DFS) (Chapter 22.3 from the book). For graph representation, you should use adjacency lists. You also have to:
Implement the Tarjan algorithm for detecting strongly connected components (https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm)
Implement topological sorting (described in chapter 22.4)
1. Set |V| = 100 and vary |E| between 1000 and 5000, using a 100 increment. Generate the input graphs randomly – make sure you don’t generate the same edge twice for the same graph. Run the DFS algorithm for each <|V|, |E|> pair value and count the number of operations performed; generate the corresponding chart (i.e. the variation of the number of operations with |E|).
2. Set |E| = 9000 and vary |V| between 100 and 200, using an increment equal to 10. Repeat the procedure above to generate the chart which gives the variation of the number of operations with |V|.
3. Interpret your charts.
