思考题
给定一系列网络之间的关系，若1与2连通，2与3 连通那么1与3就是连通的，问能否找到一个节点使它 故障后导致整个网络都崩溃，输出找到的点以及故障 后禅僧的连通的子网络数。
思考题
一国有n个党派，每个党派在议会中都有2个代表， 现要组建和平委员会，要从每个党派在议会的代表中 选出1人，一共n人组成和平委员会。已知有一些代表 之间存在仇恨，也就是说他们不能同时被选为和平委 员会的成员，现要你判断满足要求的和平委员会能否 创立？
2.割点和桥
证明： 如图，考虑u的任意子结点v。 如果v及其后代不能连回f，则删除 u之后，f和v不在联通； 反之，如果v或者它的某一个后代 存在一条反向边连回f，则删除u之 后，以v根的整棵子树中的所有结 点都可以利用这条反向边与f连通。 如果所有子树中的结点都和f连通， 根据“连通”关系的传递性，整 个图就是连通的。
3.强连通分量
Kosaraju算法
3 12 11 8 10 9 6 2 1
7
5
4
第一遍DFS进行标号，根据搜索的顺序不同，标号结果也不同
3.强连通分量
Kosaraju算法
3
12
11
8
9
6
2
10
7 反向之后的图
5
4
1
11 12 8,9, 10
2,3
5,6, 7
4
1
根据反向后的图，确定联通分量
3.强连通分量
w u v w u v
? 图1
? 图2
3.强连通分量
Tarjan算法代码实现
思考题
某省调查城镇交通状况，得到现有城镇道路统 计表，表中列出了每条道路直接连通的城镇。省 政府“畅通工程”的目标是使全省任何两个城镇 间都可以实现交通（但不一定有直接的道路相连， 只要互相间接通过道路可达即可）。问最少还需 要建设多少条道路？Βιβλιοθήκη A BABD
(2, 11)
(3, 10) F (8, 9)
C
D
(4, 7) C
E 图1 F E
黑色的边称为树边 红色的箭头称为返祖边(或者叫反向边)
(5, 6)
图2
2.割点和桥
d.定理
在无向连通图G的DFS树中， 非根节点u是G的割 点当且仅当u存在一个子节点v，使得v及其后代都没 有反向边连回u的祖先(不含u)。
1.并查集
1.并查集
2.割点和桥
a. 概念 割点: 在无向联通图G = (V, E)中, 如果删除一个 点u及其相关的边, 会使得新的图不连通, 那么 点u就称为图G的一个割点
桥(割边): 在无向联通图G = (V, E)中, 如果删除 一条边e = (u, v)后, 会使得新的图不连通, 那么边 e = (u, v)就称为图G的桥, 又称为割边
3
2,3 ,4 6 8 7 1 8
4
5
5,6 ,7
问题：我们应该如果求解有向图的各个强连通分量呢？
我们再次借助DFS，如图，如果我们从8开始DFS，将得到只 包含{8}的一棵DFS树; 从5出发，得到{5, 6, 7}; 再从2出发， 得到{2,3,4}; 从1出发，得到{1}。可以发现我们“轻而易举” 的就得到了SCC。细心的同学会发现，这种方式与遍历的顺序有 着极大的关系。
Kosaraju算法的实现
3.强连通分量
3.强连通分量
3.强连通分量
Tarjan算法
我们不难发现，Kosaraju算法是借助与遍历顺序来将不同的 SCC分离到不同的DFS树中。
我们可以考虑连通分量C，设其中第一个被发现的结点为x，则 C中其他结点都是x的后代。如果我们在x访问完成时立刻输出C。 那么我们就可以在同一颗DFS树中区分开所有的SCC了。 因此这时我们将问题转化为，如何判断一个点是否为一个SCC 中最先被发现的点。
3.强连通分量
Tarjan算法
假设我们正在判断结点u是否为某个 SCC第一个发现的结点。如果我们发现从 结点u的子结点出发可以到达结点u的祖先 w，显然u，v，w在同一个SCC中，因此结 点u不是该SCC中第一个被发现的结点(如 图1所示)；另一方面，如果从结点v发现 最多只能到结点u，那么结点u是该SCC中 第一个被发现的结点(如图2所示)。
1.并查集
a.初始化
1 2 3 4 5
1.并查集
b. 合并
1 2 2 样例1 1 2 3 4 4 1
5 样例2 6 2
1
3
5
6
1.并查集
c.查询
2 3 的根是 1 5 4 1 5 2 3 6 6 的根是 4
1.并查集
d.代码实现
1.并查集
1.并查集
1.并查集
1.并查集
e.问题1
1 2 3 4 5 6
b.性质
• 一个有向环是最简单的强连通图。
• 如果一个有向图G的所有强连通分量都只有一个点，那么这 个图是有向无环图，即存在拓扑序。
3.强连通分量
c.强连通分量分解
任意的有向图都可以分解成若干不相交的强连通分量， 这就是强连通分量分解。把分解之后的强连通分量缩成一个 顶点，我们就得到了一个DAG(有向无环图)。 1 2
2.割点和桥
b. 性质
• 一个无向连通图, 如果没有割点, 那么任意两 点之间, 都存在点集互不相交(除了起点与终 点外)的两条路径 • 一个无向连通图, 如果没有桥, 那么任意两点 之间, 都存在边集互不相交的两条路径
2.割点和桥
1 2 3
4
5
1
2
6
3
4
5
图1
图2
2.割点和桥
问题: 那么我们该如何求解割点(桥)呢？
1 2
3 2,3 ,4 6 8 7 1 5,6 ,7
4
5
8
3.强连通分量
Kosaraju算法
我们可以通过两次DFS实现强连通分量分解。 第一次DFS时，选取任意顶点作为起点，遍历所有未访问的顶 点，并在回溯前给顶点标号(post order, 后序遍历)。对于其他 剩余的未访问的顶点，不断重复以上过程。完成标号后，越接近 图的尾部(搜索树的叶子)，顶点的标号越小。 第二次DFS时，先将所有边反向，然后从标号最大的顶点为起 点就行DFS。这样每次DFS所遍历的顶点集合就构成了一个强连通分 量。对于其他剩余的未访问的顶点，不断重复以上过程。 该算法只进行了两次DFS，故时间复杂度为O(|V|+|E|)
2.割点和桥
g. 代码(以割点为例)
2.割点和桥
2.割点和桥
3.强连通分量
a.概念
一个有向图G = (V, E)被称为强连通图，当且仅当图中任 意两点间都存在一条路径。即对于图中任意两点u和v，存在 u到v的路径和v到u的路径。 强连通分量(Strongly Connected Component, SCC)是指一个 有向图G的一个极大强连通子图。
• 尝试删除每个节点(边)，然后用DFS判断 连通分量是否增加 时间复杂度O(V(V+E))
• 深入挖掘DFS的性质，在线性时间(即O(V+E) 时间)内求解所有的割点(桥)
2.割点和桥
(1, 12)
c. DFS树
对图1进行DFS就能得到图 2(不唯一)，图2就称为图1 的DFS树，又称为深搜树 每个节点都有一对数字(x,y) x表示第一次访问该点的次序 y表示第二次访问该点的次序
f f
u v v
u
图1
图2
2.割点和桥
f. 实现
为了方向起见，pre[u]为u在DFS树的先序遍历的顺序， low[u]为结点u及其后代所能连回的最早祖先的pre值。
{
min(low[u],low[v]) min(low[u],pre[v])
(u,v)为树边 (u,v)为返祖边且v不是u的父节点
于是我们可以将定理写成： 当节点u存在一个子结点v，使得low[v] ≥ pre[u]，那么结点u就为 割点。另外，不难发现当low[v] > pre[u]时，那么 e = (u, v)即为桥 (割边)。
图的连通性问题
内容概要
• 并查集 • 割点和桥
• 强连通分量
• Tarjan
• Kosaraju
1. 并查集
• 并查集是一种用来管理元素分组的数据结构
• 并查集使用树形结构进行存储
• 并查集具有两个操作:
• 查询元素A和元素B是否属于同一个分组 • 合并元素A和元素B所在的分组
注意: 并查集虽然能够进行合并操作, 但却无法进行分割操作
思考题
曹操在长江上建立了一些根据地，根据地之间 有一些桥连着。如果这些根据地之间，互相可达， 那么曹操就获得战争的胜利。刘备为了防止曹操 获胜，就打算去摧毁连接曹操的根据地的桥。但 是诸葛亮把所有炸弹都带走了，只留下一枚给刘 备。所以刘备只能炸一条桥。问刘备能够阻止曹 操吗？
思考题
在A市中村与村之间的道路全是单行路，随着经 济的发展，国家启动了“村村通”工程。工程要求 任意两个村之间必须能够互相可达。给定已经存在 的道路，问至少需要修多少条路，才能实现“村村 通”。
1
2
3
4
5
6
1.并查集
f.优化1
4
1.并查集
e.问题2
2 4 1 3 方式1 1 2 3 5 2 6 方式2 3 4 5 6 5 6
1
1.并查集
f.优化2 • 对于问题2, 我们可以记录每个树的高度 • 合并时, 如果两棵树的高度不同
• 那么我们将高度低的树合并到高度高的树
1.并查集
g.优化后的代码