# 一、綜述
定義：
# 二、代碼
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter22/section22_5.cpp
# 三、練習
### 22.5-1
不變或減少
### 22.5-2
第一次DFS結果：
r u q t y x z s v w
G轉置的結果：
q:y
r:
s:q w
t:q
u:r
v:s
w:q v
x:t z
y:r t u
z:x
第二次DFS的結果：
r
u
q y t
x z
s w v
### 22.5-3
簡化后的算法不可行，證明如下。
在原算法中，過程總結為這樣幾步
（1）對圖G作DFS，計算每個點的結束時間f
（2）將結點以f遞減排序
（3）對圖作轉置，得到GT
（4）以f遞減順序對GT作DFS
（5）第二次DFS后得到的一個樹里的點都屬于同一個強聯通分支
如果以DFS后的f遞減排序，排序的結點有規律呢？
假設f[u]>f[v]，那么u和v的關系可能有幾下四種情況
（1）u和v互相不可達
（2）u和v互相可達，即在同一個聯通分支內
（3）u到v可達 && v到u不可達
（4）u到v不可達 && v到u可達 && (v,u)不是G中的邊 && 存在另一個結點w && w與v在同一個聯通分支 && w到u可達 && f[w]>f[u]>f[v]
以下將針對這四種情況做第（3）（4）操作，看是否能得到第（5）的結果
<table style="border-collapse: collapse; table-layout: fixed; margin-left: 0px;" height="242" width="865"><tbody><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.37278106508876%;"><div>對G做DFS后，f[u]>f[v]，u和v的關系</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.25443786982248%;"><div>在GT中u和v的關系</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.25443786982248%;"><div>在GT中對u做DFS，v是否會成為u的后繼</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相不可達</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相不可達</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不會</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相可達，即在同一個聯通分支內</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相可達，即在同一個聯通分支內</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>會</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v可達 && v到u不可達</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v不可達 && v到u可達</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不會</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v不可達 && v到u可達</div><div>&& (v,u)不是G中的邊</div><div>&& 存在另一個結點w && w與v在同一個聯通分支</div><div>&& w到u可達 && f[w]>f[u]>f[v]</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v可達 && v到u不可達</div><div>&& (u,v)不是G中的邊 &&</div><div>存在另一個結點w && w與v在同一個聯通分支 &&</div><div>u到w可達</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不會。</div><div>雖然u到v可達。但由于f[w]<f[v]，會先對w做DFS，v已經是w的后繼了，所以不會成為u的后繼</div></td></tr></tbody></table>
由此可以知道，以f遞減的順序對GT作DFS，同一個連通分支的點會到一棵不樹上，不是同一個連通分支的點不會到一棵樹上。
再看本題的算法過程，總結為以下幾步：
（1）對圖G作DFS，計算每個點的結束時間f
（2）將結點以f遞增排序
（3）以f遞增的順序對GT作DFS
（4）第二次DFS后得到的一個樹里的點都屬于同一個強聯通分支
與上述步驟類似，我們先分析f遞增排序后結點的關系，然后針對這些關系做第（3）步，分析是否能得到第（4）步的結果
<table style="border-collapse: collapse; margin-left: 0px; table-layout: fixed;" height="242" width="646"><tbody><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:50.05917159763313%;"><div>對G做DFS后，f[u]<f[v]，u和v的關系</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:49.82248520710059%;"><div>在G中對u做DFS，v是否會成為u的后繼</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相不可達</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不會</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相可達，即在同一個聯通分支內</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>會</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v不可達 && v到u可達</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不會</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v可達 && v到u不可達</div><div>&& (u,v)不是G中的邊</div><div>&& 存在另一個結點w && w與u在同一個聯通分支</div><div>&& w到v可達 && f[w]>f[v]>f[u]</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>會。</div><div>此處不對。u和v不屬于同一個聯通分支，但v會成為u的后繼</div></td></tr></tbody></table>
因此該算法不可行。
### 22.5-5
見[算法導論 22.5-5 O(V+E)求有向圖的分支圖](http://blog.csdn.net/mishifangxiangdefeng/article/details/8461683)
### 22.5-6
待解決，題目的意思不太懂，網上找了個答案，主要是其中的第四步不懂。
令所求圖為G2，翻譯一下：
STEP1：使用22.5中的算法計算出所有的強連通分支
STEP2：使用22.5中和算法計算出分支圖G|SCC
STEP3：將G2的邊集初始化為空
STEP4：將每個強連通分支中的頂點構成環。比如強連通分支a中有ea1,ea2,ea3,ea4這四個頂點，就在G2中加入邊ea1->ea2,ea2->ea3,ea3->ea4,ea4->ea1
STEP5：把分支圖的邊加到G2中。比如分支圖中有一條強連通分支a到強連通分支b的邊，就在G2中加入一條ea到eb的邊。其中ea是a中的任意一個頂點，eb是b中的任意一個頂點
解釋：
強連通分支：
分支圖：
G與G2有相同的強連通分支 ===>?? G2的頂點與G的頂點相同
G與G2有相同的分支圖???? ===>?? G2至少有著G|SCC中的邊?? ===>?? STEP5
G2有最小的邊??????????? ===>?? 具有最少邊的強連通圖是一個環，邊的個數與頂點的個數相同?? ===>?? STEP4
### 22.5-7
STEP1：使用22.5-5中的算法得到SCC。
STEP2：對SCC求拓撲序列(v1, v2, ……, vk)
STEP3：若在邊SCC中存在邊(v1,v2),(v2,v3),……,(vk-1,vk)，則圖G為半連通。
- 前言
- 第6章 堆排序
- 6-3 Young氏矩陣
- 第7章 快速排序
- 第8章 線性時間排序
- 第9章 排序和順序統計學算法導論
- 算法導論 9.1-1 求第二小元素
- 第10章 10.1 棧和隊列
- 第10章 10.2 鏈表
- 第10章 10.3 指針和對象實現
- 第10章 10.4 有根樹的表示
- 第11章-散列表
- 第12章 二叉查找樹
- 第13章 紅黑樹
- 第14章 14.1 動態順序統計
- 算法導論-14-1-最大重疊點
- 算法導論-14-2-Josephus排列
- 第14章 14.3 區間樹
- 第15章 動態規劃
- 第16章 貪心算法
- 第18章 B樹
- 第19章-二項堆
- 第20章 斐波那契堆
- 第21章 用于不相交集合的數據結構
- 第22章 圖的基本算法 22.1 圖的表示
- 第22章 圖算法 22.2 廣度優先搜索
- 第22章 圖算法 22.3 深度優先搜索
- 第22章 圖的基本算法 22.4 拓撲排序
- 第22章 圖的基本算法 22.5 強聯通分支