Homework 9-7
=
###### tags: `Course - Algorithmics`
## Design
1. 先對原本的無向圖做一次DFS，就可以先決定好「暫定的」有向圖$G$。
2. 方向是由parent到child，如果有back edge就從descendant到ancestor。
3. 把$G$用Exercise 22.1-3的方法反向得到$G^T$。
4. 以上面DFS Tree中最「深」的點(即finish[]最小的點)做為起點，對$G^T$做DFS。
5. 如果有走不到的點就代表$G$不是strongly connected graph。
e.g.
## Pseudo Code
* Initialize

def init():
    for l in adj:
        for v in l:
            disc[v] = -1
            finish[v] = 0
    counter = 0

* Get $G$

def dfs_undirect(u, v): # v is the parent of u (if any)
    disc[u] = counter
    counter++
    for w in adj[u]: # u's Adjacency list
        if disc[w] < 0: # w is u's child in DFS tree
            adj[w].remove(u) # make the edge single direction
            dfs_undirect(w, u)
        else: # edge(u, w) is a back edge in DFS tree
            adj[u].remove(w) # make the edge single direction
    finish[u] = counter
    counter++

* Get $G^T$

def transpose():
    adj_T[]
    for l in adj:
        for v in l:
            adj_T[v].append(l.begin)
    adj = adj_T

* DFS $G^T$

def dfs_direct(u, v): # v is the parent of u (if any)
    disc[u] = counter
    counter++
    for w in adj[u]: # u's Adjacency list
        if disc[w] < 0: # w is u's child in DFS tree
            dfs_direct(w, u)

* Main function

input g
create adj[]
init()
dfs_undirect(adj.begin.begin, Null)
transpose()
starting_vertex = argmin(finish)
init()
dfs_direct(starting_vertex, Null)
for i in disc:
    if i == -1:
        print("Impossible.")
        exit()
print(adj)

## Analysis
Let n = |V|, m = |E|
* Time complexity:
Same as DFS for adjacency list representation of graph.
$\Theta(n + m)$
* Space complexity:
Size of disc[] and finish[] are both n
Size of adjacency list is (n + m)
Therefore, it's $\Theta(n + m)$