---
# System prepended metadata

title: Homework 10-5
tags: [Course - Algorithmics]

---

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，反之就不用做任何修改。
* 示意圖
![](https://i.imgur.com/PlLHwIo.png)
![](https://i.imgur.com/ErXalaU.png)
-- --
方法1:
* 因為這題有許多環，所以要刪除的邊不只一個，不可能只記錄一個邊就能解決，所以要把所有的環都找出來。
* 以下是找環的方法：
    * 沒有重疊的環: 
        1. 建立adjacency list
        2. 做DFS，但是節點要分成白(未拜訪)、灰(已拜訪，但其descendant尚未完全拜訪完)、黑(其descendant已經全部拜訪完)三色。
        3. 如果遇到灰色的節點代表有環形成，就要往回走一圈，並把沿途的節點全歸類在同一個環上。
    * 有重疊的環:
        *  NP-C問題，不存在有效率的演算法。
* 然後把每個環中最大的邊給刪除就完成了。
* 示意圖:
![](https://i.imgur.com/9mT4ssb.png)
![](https://i.imgur.com/6ahTwgC.png)
![](https://i.imgur.com/ZQg66ZP.png)
-- --
方法2:
* 從新插入的節點(以下簡稱N)開始DFS，並把拜訪過的邊依照「拜訪順序」放入一個Linked List(以下簡稱L)，這時會遇上兩種情況：
* Case1: 走到底了(adj[u].length == 1)，這時就要從上一個岔路處出發(需要用Stack存上個岔路的位置)，並且刪除L在岔路後所有的邊。
* Case2: 走回N，這時就從L中找出權重最大的邊從圖刪掉，然後把他後面所有的邊都從L刪掉，Stack也需刪除對應的點。再來是開一個新的空Linked List(L1)，把終點到上個岔路的邊全部反向放入L1，然後從上個岔路出發。
* 示意圖(因為畫好後才發現有錯，請見諒):
![](https://i.imgur.com/nPgO2L1.png)
(branch裡的2和L裡的(4,2,4)應該要刪掉)
![](https://i.imgur.com/UGPSDaF.png)
(branch裡的2和L裡的(4,2,4)應該要刪掉)
![](https://i.imgur.com/QqL7RJq.png)
(branch裡的2和L裡的(4,2,4)應該要刪掉)
![](https://i.imgur.com/UE4hUMU.png)
(branch為空，所以全部刪掉)
![](https://i.imgur.com/ue3R7db.png)
(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)$.