Homework 8-7
=
###### tags: `Course - Algorithmics`
## Design
1. First, we need to find the depth first spanning tree of the connected undirected graph.
2. Define `disc(u)`: the DFS visit sequence of vertex u.
For example, `disc(4) = 1` in the following picture
3. Define `low(u)`: the lowest `disc()` that we can reach from u using a path of descendants followed by at most one back edge (nontree edge).
:::info
$low(u) = min(disc(u),$
                        $min_{w:u.child}(low(w)),$
                        $min_{edge(u,w):u.backEdge}(disc(w)))$
P.S.
* u.child is a set of u's children
* u.backEdge is a set of back edges containing u

Can be simplified as:
$low(u) = min(disc(u),disc(w))$
Where w is an ancestor of u and there is a back edge from some descendant of u to w.
:::
       For example, `low(4) = 0` in the following picture
       (because vertex 1 is vertex 4's descendant and edge(1, 3) is a back edge)
       
4. Any vertex u is an articulation point if and only if:
* Case 1: u is the root of the spanning tree and has two or more children
* Case 2: u is not the root and has at least one child w such that we cannot reach an ancestor of u using a path that consists of only
1. w
2. descendants of w
3. a single back edge
* thus, low(w) ≥ disc(u)
* explain:

## Pseudo Code
Assume there are n vertices in the given connected undirected graph g.
* Initialize

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

* Calculate disc() and low() by recursion

def calc_disc_low(u, v): # v is the parent of u (if any)
    disc[u] = counter
    low[u] = counter
    counter++
    for w in adj[u]: # u's Adjacency list
        if disc[w] < 0: # w is u's child in DFS tree
            calc_disc_low(w, u) # get low[w] by recursion
            t = min(disc[u], low[w])
        elif w != v: # edge(u, w) is a back edge in DFS tree
            t = min(disc[u], disc[w])
        # else, do nothing
        if t < low[u]: # update low[u]
            low[u] = t

* Find articulation points by modifing calc_disc_low()

def find_AP(u, v): # v is the parent of u (if any)
    child = 0 # how many children u have
    disc[u] = counter
    low[u] = counter
    counter++
    for w in adj[u]: # u's Adjacency list
        if disc[w] < 0: # w is u's child in DFS tree
            child++
            find_AP(w, u) # get low[w] by recursion
            t = min(disc[u], low[w])
            if v == Null & child > 1: # articulation point case 1
                ap[u] = True
            if low[w] >= disc[u]: # articulation point case 2
                ap[u] = True
        elif w != v: # edge(u, w) is a back edge in DFS tree
            t = min(disc[u], disc[w])
        # else, do nothing
        if t < low[u]: # update low[u]
            low[u] = t

* Main function

input g
create adj[]
init()
find_AP(adj.begin.begin, Null)
print(ap)

## 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 low[] are both n
Size of adjacency list is (n + m)
Therefore, it's $\Theta(n + m)$