Kosaraju algorithm - computing SCCs

Question

For a given directed graph G I need to compute its strongly connected components (SCCs) using Kosaraju's algorithm. As far as I've understood the steps of the algorithm are as follows:

1. Let Grev = G wit all arcs reversed
2. Run DFS (Depth-First Search) on Grev to compute the finishing times of the nodes
3. Run DFS on G to discover SCCs

I have managed to find the correct finishing times of all the nodes. I partially understand that I should assign the finishing times to its respective node values, reverse the graph Grev, and run DFS again on the reversed graph (now G) with the finishing times as the node values processing nodes in decreasing order of finishing times. Is my understanding correct? If so, how can I code it up?

Here's where I got to so far:

# Number of elements in graph + 1
graph_elem = 10

def dfs_iterative(graph):
    # variable initialization

    for i in range(graph_elem - 1, 0, -1):
        stack.append(i)

        while stack:
            v = ... # Get top of stack

            # If the top of the stack is not explored, or if any of the children of 
            # the node on the top of the stack are unexplored, then continue the traversal
            if ...:
                #Mark explored

                for head in graph[v]:
                    if head not in explored:
                        stack.append(head)
                    # Prevent the loop iterating through all of the children like BFS

            else:
                # Get finishing time for v

    return finishing_times

# Graph represented in a list through edges
# index represents the tail node of the edge, and g[index] is the head node
# Example edges of g: (1, 4), (2, 8), (3, 6), etc.
g = [[], [4], [8], [6], [7], [2], [9], [1], [5, 6], [7, 3]]
rev_g = [[], [7], [5], [9], [1], [8], [3, 8], [4, 9], [2], [6]]
fin_times = dfs_iterative(rev_g)

The fin_times should be {3: 1, 5: 2, 2: 3, 8: 4, 6: 5, 9: 6, 1: 7, 4: 8, 7: 9}, and as previously mentioned it is correct. What do I actually have to do with fin_times now?

Also, the reason I am doing it iteratively and not recursively is the fact that the input file for the assignment is too big and the program would reach recursive limits.

Edit: Upon answering the question I realized that the question was not in accordance with the course's Honor Code. I edited the question to exclude parts of the code that may give away the solution to the assignment.

Answer 1

Since my question was only:

What to do with the fin_times dictionary?

I'll provide the solution only to that question as to not offer the complete solution to the assignment.

So the answer seemed to be reversing the fin_times dictionary so that the keys become the values, and vice-versa:

order = dict((v, k) for k, v in finishing_times.items())

{1: 3, 2: 5, 3: 2, 4: 8, 5: 6, 6: 9, 7: 1, 8: 4, 9: 7}

Then we run DFS on G processing nodes in decreasing order of finishing times (in this case vertex 7 with the finishing time 9). Corresponding to the code in the question, instead of:

for i in range(graph_elem - 1, 0, -1):
        stack.append(i)

We write:

order = dict((v, k) for k, v in finishing_times.items())

for i in range(graph_elem - 1, 0, -1):
        vertex = order[i]
        if vertex not in explored:
            stack.append(vertex)
            explored.add(vertex)

            // DFS code and SCC size computation...