Homework 10-5
=
###### tags: `Course - Algorithmics`
## Design
* 這題可以看作是第二題(更新某個不在MST裡的邊之權重)的延伸，因為第二題只會有一個環，但這題會有許多環，所以需要修改第二題用的方法。
* 先來看一下第二題的作法，假設更新了權重的邊是$e(v_1, v_2)$，就從$v_1$和$v_2$同時找parent，直到抵達root，並把經過的最大權重邊記錄下來，如果此邊的權重大於$e(v_1, v_2)$就刪除此邊，然後把$e(v_1, v_2)$插入MST，反之就不用做任何修改。
* 示意圖
-- --
方法1:
* 因為這題有許多環，所以要刪除的邊不只一個，不可能只記錄一個邊就能解決，所以要把所有的環都找出來。
* 以下是找環的方法：
* 沒有重疊的環:
1. 建立adjacency list
2. 做DFS，但是節點要分成白(未拜訪)、灰(已拜訪，但其descendant尚未完全拜訪完)、黑(其descendant已經全部拜訪完)三色。
3. 如果遇到灰色的節點代表有環形成，就要往回走一圈，並把沿途的節點全歸類在同一個環上。
* 有重疊的環:
* NP-C問題，不存在有效率的演算法。
* 然後把每個環中最大的邊給刪除就完成了。
* 示意圖:
-- --
方法2:
* 從新插入的節點(以下簡稱N)開始DFS，並把拜訪過的邊依照「拜訪順序」放入一個Linked List(以下簡稱L)，這時會遇上兩種情況：
* Case1: 走到底了(adj[u].length == 1)，這時就要從上一個岔路處出發(需要用Stack存上個岔路的位置)，並且刪除L在岔路後所有的邊。
* Case2: 走回N，這時就從L中找出權重最大的邊從圖刪掉，然後把他後面所有的邊都從L刪掉，Stack也需刪除對應的點。再來是開一個新的空Linked List(L1)，把終點到上個岔路的邊全部反向放入L1，然後從上個岔路出發。
* 示意圖(因為畫好後才發現有錯，請見諒):
(branch裡的2和L裡的(4,2,4)應該要刪掉)
(branch裡的2和L裡的(4,2,4)應該要刪掉)
(branch裡的2和L裡的(4,2,4)應該要刪掉)
(branch為空，所以全部刪掉)
(result)
## Analysis
Let n = |V|, m = |E|, but $m ≤ ((n - 1)\times2 - 1)$
方法1:
* Time complexity:
* 如果沒有重疊的環:
$\Theta(3n)$
* 有重疊的環:
There will be $(n - 2)!$ cycles in the worst case, so it's hard to calculate (maybe $\Theta(n!)$).
* Space complexity:
* 如果沒有重疊的環:
Size of visted[], parent[], and group[] are both n
Size of adjacency list is 3n
Therefore, it's $\Theta(3n)$
* 有重疊的環:
Hard to calculate.
-- --
方法2:
Hard to calculate, probably $\Theta(n^2)$, because find maximum and delete in linked list are both $\Theta(n)$.