# HW9 - Q5
###### tags: `演算法`, `109-2`

## Question
**Exercises 22.5-7**
A directed graph $G = (V, E)$ is ***semiconnected*** if, for all pairs of vertices $u$, $v ∈ V$, we have $u$ ~> $v$ or $v$ ~>$u$. Give an efficient algorithm to determine whether or not $G$ is semiconnected. Prove that your algorithm is correct, and analyze its running time.

## Mein Answer
<!--  -->

Hmmm...從 semiconnected 的定義看，看起來有種莫名的既視感... 是什麼呢？

> **Strongly Connect Component (SCC):**
> Maximal set of vertice $C \subseteq V$,
> for all pairs of vertices $u$, $v ∈ C$, we have $u$ ~> $v$ **and** $v$ ~>$u$

嗯，就差這麼一點點。但是差這一點就差很多了！對於 SCC 的世界裡，必須要能「你來我往」才能成立，但是對於本題 semiconnect，一廂情願也是可以接受的，正如現實與虛擬的單向鏡，我廚我的角色，即使隔著一個次元的距離，心心相印的感情依舊能打破象限的藩籬，沒問題的 :100:

幹話那麼多，其實 SCC 的解法在這裡用不上對吧？呃，應該是吧
那我提到他幹嘛？ 我就記在這裡期末複習說不定會看到啊 (雖然高機率不會只是我看到啦666)
總之，來為各位介紹我的 ~~奮鬥~~ 解法

### Mein Algo
搭配範例解釋，文組學生(如我)較為舒適

我們先把問題化小一點，如何化小？找 SCC 們！ (還是用到了ww)
再把他們集合成新圖(也就是 Component Graph)！而因為 SCC 裡面的碗糕都是相互連通的，所以我們可以篤定每個 SCC 也是 semiconnected。


有了Component Graph，我們可以做什麼？
要回答這個問題，我們要問：我們要解的是什麼？我們學演算法的初衷又是什麼？
> 我只是不想被當掉 要重修很麻煩
> [name=JCxYIS]

我們要比較每個 SCC 之間是不是真的有相連，而且因為我們現在持有的不是一般的圖，而是 Component Graph，也就是沒有環，很 DAG 的那種。說到 DAG 會想到要做什麼？
拓樸排序！
拓樸排序後，因為他是依照潮流順序一波波向後排，我們只要檢查相鄰每個 vertrice 之間有沒有內痔外痣連在一起，就能確定有沒有「藉由第三者的關係連繫到你」綠帽情況發生，如果有，就表示有一個 component 不是 semiconnected，臭負心漢。

### Pseudo Code

IsSemiConnected(Graph G):
    G' = Component Graph of G
    v[] = TopologicalSort(G').vertices    
    for i in (0 to v.length):
        if !(v[i] has no edge to v[i+1])
            return false  
    return true 

#### Complexity
> 依錦文所好，以下稱 $n = V 的數量$、$m = E 的數量$
>
Time Complexity:
Construct Component Graph: O(n+m) (using 2 DFSs)
Perform Topological Search: O(n+m)
View through the accompany verts: O(n+m)
Overall: $O(n+m)$

### References
- https://www.geeksforgeeks.org/strongly-connected-components/
- http://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html
- https://blog.csdn.net/anye3000/article/details/9791213
- https://titanwolf.org/Network/Articles/Article?AID=bc9d9c20-fbbf-42d6-a0e5-123300cb766d#gsc.tab=0
- http://alrightchiu.github.io/SecondRound/graph-li-yong-dfshe-bfsxun-zhao-connected-component.html
- http://alrightchiu.github.io/SecondRound/graph-depth-first-searchdfsshen-du-you-xian-sou-xun.html
- https://alrightchiu.github.io/SecondRound/graph-li-yong-dfsxun-zhao-dagde-topological-sorttuo-pu-pai-xu.html