Kosaraju in Python

Questions 1 to 5 of 7

1. 1. Put the three stages of Kosaraju's algorithm in the order the program runs them.

   Use the arrows to put the steps in order.

   1. 1.Walk the vertices from the last finish time to the first on the reversed graph, labelling each walk as one component.↑↓
   2. 2.Run depth-first search on the original graph and record each vertex when its call finishes.↑↓
   3. 3.Turn each label's vertices into one node to build the condensed graph.↑↓
2. 2. The arrows go from 0 to 1 and from 0 to 2. Pass 1 starts at vertex 0. Put the three finish events in the order they happen.

   Use the arrows to put the steps in order.

   1. 1.The call for vertex 0 finishes.↑↓
   2. 2.The call for vertex 1 finishes.↑↓
   3. 3.The call for vertex 2 finishes.↑↓
3. 3. On the eight-vertex graph from the lesson, a program runs pass 2 on the reversed graph but walks the finish list from the first entry instead of the last. What does it report?

   Two components are reported, and the walk from vertex 6 swallows the group 3, 4, 5.The output is unchanged, because the order of the finish list does not affect pass 2.Everything is reported as one component, because vertex 5 comes first in the finish list and its reversed walk reaches the whole graph.Eight components are reported, one per vertex, because the reversed walk never leaves its start.
4. 4. Why does the last vertex to finish in pass 1 start a walk that labels exactly one component?

   It has the most arrows leaving it, so its reversed walk reaches the most vertices.No arrow from an unlabelled group points into its group, so the reversed walk cannot leave the group.It is always vertex 0, so its component is the first one labelled.Its group is always the biggest component in the graph.
5. 5. What does this program print? ``python adj = [[] for _ in range(4)] seen = [False] * 4 finish = [] def dfs(u): seen[u] = True for v in adj[u]: if not seen[v]: dfs(v) finish.append(u) adj[0].append(1) adj[0].append(2) adj[1].append(3) adj[2].append(3) for u in range(4): if not seen[u]: dfs(u) print(finish) ``

   [3, 2, 1, 0][0, 2, 1, 3][0, 1, 2, 3][3, 1, 2, 0]