105 年台大電機丙資結
===
>有錯歡迎留言指正

一、
1. B
2. B
3. A
4. B
5. B
6. A
7. A
8. B
9. A
10. B
11. C
12. C
13. E
14. E

三、懶得寫
四、
可能還有更快的解法但我想不到 Q
**直覺解法** :
定義一個 n * n 二維陣列 arr 儲存 $f(a_i, a_j)$ 之值。
CreateTable(arr) : 計算所有 $f(a_i, a_j)$ 之值，同時間紀錄最小值。時間複雜度為 $O(n^2)$。

min = ∞
for i = 1 to n
    for j = 1 to n
        arr[i][j] = f(a_i, a_j)
        if arr[i][j] < min
            min = arr[i][j]

Update($a_i$, value): 每當 $a_i$ 要更新成 value 時，就呼叫此函數。此函數會更新 $f(a_i, a_j)$ 和 $f(a_j, a_i)$ for j = 1 ~ n，共 2n 筆資料，時間複雜度為 $O(n)$。

a_i = value
for j = 1 to n
    arr[i][j] = f(a_i, a_j)
    arr[j][i] = f(a_j, a_i)

題目要求更新 m 次資料，所以從建立二維陣列到完成 m 次更新所需之時間為 $O(n^2+mn)$。
若 m > n，則時間為 $O(mn)$；若 m <= n，則時間為 $O(n^2)$。
五、
利用 Tarjan's 演算法
1. DFS
2. 拜訪階段，針對每點，計算自己和子孫所能觸及的最高祖先。觸及是指 : 不斷走任意邊但不能走到曾經形成的 SCC。
3. 回溯階段，每當發現某點恰是最高祖先，即表示這點和子孫已形成 SCC。從堆疊中刪除 SCC 免得再次處理。

令 adj[n][n] 為 adjacency matrix
令 visit[n] 表示拜訪該節點的時間
令 Instack[n] 紀錄該點是否在堆疊中

DFS(i, parent){
    visit[i] = low[i] = True
    time++
    stack.push(i)
    for i = 1 to n
        if(adj[i][j])
            if(visit[j] == 0) DFS(j, i)
            if(j != parent) low[i] = min(low[i], low[j])
    if(visit[i] = low[i])
        do
            k = stack.pop()
            print(k)
        while(i != k)
}

時間為一次 DFS 走訪的時間，且用 adjacency matrix，故為 $O(V^2)$