How can the number of strongly connected components of a graph change if a new edge is added?
Answer:
A directed graph is strongly connected if every two vertices are reachable from each other. If a new edge is added then we have two scenarios of result
Show how the procedure STRONGLYCONNECTEDCOMPONENTS works on the graph of finger 22.6. Specially, show the finishing times computed in line 1 and the forest procedure in line 3. Assume that the loop of line 57 of DFS considers vertices in alphabetical order and that the adjacency lists are in alphabetical order.
Answer:
Run DFS(G). When DFS returns, every vertex u has been assigned a discovery time d[u] and a finish time f[u].

q 
r 
s 
t 
u 
v 
w 
x 
y 
z 
f[u] 
16 
20 
7 
15 
19 
6 
5 
12 
14 
11 











Compute G^{T} to get the adjacency list:
Run DFS(G^{T}) in order

r 
u 
q 
t 
y 
x 
z 
s 
v 
w 
f[u^{T}] 
2 
4 
8 
9 
10 
13 
14 
18 
19 
20 
Reorder f[u] and f[u^{T}] we have the strongly connected components as:

r 
u 
q 
t 
y 
x 
z 
s 
v 
w 

20 
19 
16 
15 
14 
12 
11 
7 
6 
5 
f[u^{T}] 
2 
4 
8 
9 
10 
13 
14 
18 
19 
20 
{r}, {u}, {q, y, t}, {x, z}, {s, w, v}
Exercises 22.53
Professor Deaver claims that the algorithm for strongly connected components can be simplified by using the original (instead of the transpose) graph in the second depthfirst search and scanning the vertices in order of increasing finishing time. Is the professor correct?
Answer:
Credit will go to Kathy Macropol as her answer address
all components of this question.
Also reference: http://www.cc.gatech.edu/classes/AY2003/cs3500c_spring/homework3/hwk3solution.pdf
No. As an example, consider the graph:
It's obvious by looking at it that it contains 2 strongly connected components,
{A, B}, and {C}.
Running through the algorithm:
We get the finishing times (assuming alphabetical order):
A(1
B(2,3)
C(4,5)
A(1,6)
Arranging this in order of increasing finishing times:
B(2,3) > C(4,5) > A(1,6)
And then, going through DFS with this, we get:
B > A > C
Which means we have one strongly connected component consisting of nodes A, B,
and C...which is incorrect.