强连通分支、桥和割点

Size: px

Start display at page:

Download "强连通分支、桥和割点"

浈季枝
5 years ago
Views:

1 北京大学暑期课 ACM/ICPC 竞赛训练北京大学信息学院郭炜课程网页 :

2 强连通分支桥和割点北京大学信息学院郭炜本讲义部分内容参考北京大学信息学院实验班袁洋陈科吉同学讲义, 特此致谢

3 定义在有向图 G 中, 如果任意两个不同的顶点相互可达, 则称该有向图是强连通的有向图 G 的极大强连通子图称为 G 的强连通分支

4 有向图强连通分支的 Trjn 算法做一遍 DFS, 用 dfn[i] 表示编号为 i 的节点在 DFS 过程中的访问序号 ( 也可以叫做开始时间 ) 在 DFS 过程中会形成一搜索树在搜索树上越先遍历到的节点, 显然 dfn 的值就越小 dfn 值越小的节点, 就称为越早

5 做一遍 DFS, 用 dfn[i] 表示编号为 i 的节点在 DFS 过程中的访问序号 ( 也可以叫做开始时间 ) 在 DFS 过程中会形成一搜索树在搜索树上越先遍历到的节点, 显然 dfn 的值就越小 dfn 值越小的节点, 就称为越早有向图强连通分支的 Trjn 算法用 low[i] 表示从 i 节点出发 DFS 过程中 i 下方节点 ( 开始时间大于 dfn[i], 且由 i 可达的节点 ) 所能到达的最早的节点的开始时间初始时 low[i]=dfn[i]

6 做一遍 DFS, 用 dfn[i] 表示编号为 i 的节点在 DFS 过程中的访问序号 ( 也可以叫做开始时间 ) 在 DFS 过程中会形成一搜索树在搜索树上越先遍历到的节点, 显然 dfn 的值就越小 dfn 值越小的节点, 就称为越早有向图强连通分支的 Trjn 算法用 low[i] 表示从 i 节点出发 DFS 过程中 i 下方节点 ( 开始时间大于 dfn[i], 且由 i 可达的节点 ) 所能到达的最早的节点的开始时间初始时 low[i]=dfn[i] DFS 过程中, 碰到哪个节点, 就将哪个节点入栈栈中节点只有在其所属的强连通分量已经全部求出时, 才会出栈

7 有向图强连通分支的 Trjn 算法如果发现某节点 u 有边连到栈里的节点 v, 则更新 u 的 low 值为 min(low[u],dfn[v]), 若 low[u] 被更新为 dfn[v], 则表明目前发现 u 可达的最早的节点是 v.

8 有向图强连通分支的 Trjn 算法对于 u 的子节点 v, 从 v 出发进行的 DFS 结束回到 u 时, 使得 low[u] = min(low[u],low[v]) 因为 u 可达 v, 所以 v 可达的最早的节点, 也是 u 可达的如果一个节点 u, 从其出发进行的 DFS 已经全部完成并回到 u, 而且此时其 low 值等于 dfn 值, 则说明 u 可达的所有节点, 都不能到达任何比 u 早的节点那么该节点 u 就是一个强连通分量在 DFS 搜索树中的根此时, 显然栈中 u 上方的节点, 都是不能到达比 u 早的节点的将栈中节点弹出, 一直弹到 u( 包括 u), 弹出的节点就构成了一个强连通分量.

9 有向图强连通分支的 Trjn 算法 void Trjn(u) { dfn[u]=low[u]=++index stck.push(u) for ech (u, v) in E { if (v is not visted) { trjn(v) low[u] = min(low[u], low[v]) } else if (v in stck) { low[u] = min(low[u], dfn[v]) } } if (dfn[u] == low[u]) { //u 是一个强连通分量的根 repet v = stck.pop print v until (u== v) } // 退栈, 把整个强连通分量都弹出来 } // 复杂度是 O(E+V) 的

10 (dfn,low) 栈 (1,1) b f c g d e

11 (dfn,low) 栈 (2,2) b (1,1) f c g d b e

12 (dfn,low) 栈 (2,2) (1,1) (3,3) c b g f d c b e

13 (dfn,low) 栈 (2,2) (1,1) (3,3) c b g f e c d b (4,4) e

14 (dfn,low) 栈 (3,3) c (2,2) b (1,1) g f 强连通分量 : {e} c d b (4,4) e

15 (dfn,low) 栈 (3,3) c (2,2) b (1,1) g f d 强连通分量 : {e} c d (5,5) b (4,4) e

16 (dfn,low) 栈 (3,3) c (2,2) b (1,1) g f d 强连通分量 : {e} c d (5,2) b (4,4) e

17 (dfn,low) 栈 (3,2) c (2,2) b (1,1) g f d 强连通分量 : {e} c d (5,2) b (4,4) e

18 (dfn,low) 栈 (3,2) c (2,2) b (1,1) g f 强连通分量 : {e} {b c d} d (5,2) (4,4) e

19 (dfn,low) 栈 (3,2) c (2,2) b (1,1) g f (6,6) 强连通分量 : {e} {b c d} d (5,2) f (4,4) e

20 (dfn,low) 栈 (3,2) c (2,2) b (1,1) f (6,6) g (7,7) 强连通分量 : {e} {b c d} g d (5,2) f (4,4) e

21 (dfn,low) 栈 (3,2) c (2,2) b (1,1) f (6,6) g (7,1) 强连通分量 : {e} {b c d} g d (5,2) f (4,4) e

22 (dfn,low) 栈 (3,2) c (2,2) b (1,1) f (6,1) g (7,1) 强连通分量 : {e} {b c d} { f g} d (5,2) (4,4) e

23 有向图强连通分支的 Trjn 算法为什么从 u 出发的 DFS 全部结束回到 u 时, 若 dfn[u]=low[u], 此时将栈中 u 及其上方的节点弹出, 就找到了一个强连通分量? 此时所有节点分成以下几类 : 1) 还没被访问过的节点 2) 栈中比 u 早的节点 ( 在 u 下方 ) 3) 栈中比 u 晚的节点 ( 在 u 上方 ) 4) 栈中的 u 5) 曾经入栈 ( 访问过 ), 又出了栈的节点要证明 1) 2) 5) 三类节点, 都是要么从 u 不可达, 要么不可达 u, 且 3) 4) 类节点互相可达

24 有向图强连通分支的 Trjn 算法此时所有节点分成以下几类 : 1) 还没被访问过的节点 ( 显然由 u 不可达 ) 2) 栈中比 u 早的节点 ( 由 u 不可达, 因为 low[u]=dfn[u]) 3) 栈中比 u 晚的节点 ( 由 u 可达 ) 4) 栈中的 u 5) 曾经入栈 ( 访问过 ), 又出了栈的节点 ( 不可达 u) 要证明 : 1. 第 5) 类节点不可达 u 2. 第 3) 类节点可达 u

25 有向图强连通分支的 Trjn 算法 1. 证第 5) 类节点不可达 u 此类节点分成两部分 : 1) 早于 u 的 2) 晚于 u 的早于 u 的不可达 u 若可达的话, 它此时应该还在栈里面,u 的下面 --- 导致矛盾第 2 类中, 任取节点 x, 假设 x 可达的最早节点是 y, 则 y 一定晚于 u, 即 x 不可达 u.

26 有向图强连通分支的 Trjn 算法第 2 类中, 任取节点 x x 之所以已经被弹出栈, 一定是因为最终 low[x] = dfn[x], 或在栈里,x 位于某个 y 节点上方 ( 由 y 可达, 且 y 满足条件 : 最终的 low[y] = dfn[y] 因为 y 曾经出现在 u 的上方, 所以 y 一定晚于 u 因为 low[x] 不可能小于等于 dfn[u]( 否则 low[y] 就也会小于等于 dfn[u], 这和 low[y]=dfn[y] 矛盾 ), 所以 x 到达不了 u 及比 u 早的节点 1. 证第 5) 类节点不可达 u 证毕

27 有向图强连通分支的 Trjn 算法 2. 第 3) 类节点可达 u 若有此类节点 x 不可达 u, 则考虑最终的 low[x]: low[x] < dfn[u] 不可能, 否则有 low[u]<dfn[u] low[x] = dfn[u] x 可达 u 其他 : 寻找 x 所能到达的最早的, 栈里面的节点 y, 则 y 必然比 u 晚而且有 low[y] = dfn[y]( 若此条不成立, 则 x 还能到达比 y 更早的节点, 矛盾 ) 而若 low[y] = dfn[y], 则 y 应该已经被弹出栈了,y 上方的 x 当然也已经不再栈中, 这和 x 是第 3 类节点矛盾

28 POJ2186:Populr Cows 给定一个有向图, 求有多少个顶点是由任何顶点出发都可达的顶点数 <= 10,000, 边数 <= 50,000

29 有用的定理 : 有向无环图中唯一出度为 0 的点, 一定可以由任何点出发均可达 ( 由于无环, 所以从任何点出发往前走, 必然终止于一个出度为 0 的点 )

30 POJ2186: 解题思路 1. 求出所有强连通分量 2. 每个强连通分量缩成一点, 则形成一个有向无环图 DAG 3. DAG 上面如果有唯一的出度为 0 的点, 则该点能被所有的点可达那么该点所代表的连通分量上的所有的原图中的点, 都能被原图中的所有点可达, 则该连通分量的点数, 就是答案 4. DAG 上面如果有不止一个出度为 0 的点, 则这些点互相不可达, 原问题无解, 答案为 0

31 POJ2186: 解题思路缩点的时候不一定要构造新图, 只要把不同强连通分量的点染不同颜色, 然后考察各种颜色的点有没有连到别的颜色的边即可 ( 即其对应的缩点后的 DAG 图上的点是否有出边 )

32 POJ1236: Network of Schools 题目大意 :N(2<N<100) 各学校之间有单向的网络, 每个学校得到一套软件后, 可以通过单向网络向周边的学校传输, 问题 1: 初始至少需要向多少个学校发放软件, 使得网络内所有的学校最终都能得到软件 2, 至少需要添加几条传输线路 ( 边 ), 使任意向一个学校发放软件后, 经过若干次传送, 网络内所有的学校最终都能得到软件

33 ACM1236: Network of Schools 给定一个有向图, 求 : 1) 至少要选几个顶点, 才能做到从这些顶点出发, 可以到达全部顶点 2) 至少要加多少条边, 才能使得从任何一个顶点出发, 都能到达全部顶点顶点数 <= 100

34 有用的定理 : 有向无环图中所有入度不为 0 的点, 一定可以由某个入度为 0 的点出发可达 ( 由于无环, 所以从任何入度不为 0 的点往回走, 必然终止于一个入度为 0 的点 )

35 ACM1236: 解题思路 1. 求出所有强连通分量 2. 每个强连通分量缩成一点, 则形成一个有向无环图 DAG 3. DAG 上面有多少个入度为 0 的顶点, 问题 1 的答案就是多少

36 ACM1236: 解题思路在 DAG 上要加几条边, 才能使得 DAG 变成强连通的, 问题 2 的答案就是多少加边的方法 : 要为每个入度为 0 的点添加入边, 为每个出度为 0 的点添加出边假定有 n 个入度为 0 的点,m 个出度为 0 的点, mx(m,n) 就是第二个问题的解 ( 证明难, 略 )

37 无向连通图求割点和桥无向连通图中, 如果删除某点后, 图变成不连通, 则称该点为割点无向连通图中, 如果删除某边后, 图变成不连通, 则称该边为桥

38 求桥和割点的 Trjn 算法思路和有向图求强连通分量类似在深度优先遍历整个图过程中形成的一棵搜索树 dfn[u] 定义和前面类似, 但是 low[u] 定义为 u 或者 u 的子树中能够通过非父子边 ( 父子边就是搜索树上的边 ) 追溯到的最早的节点的 DFS 开始时间

39 (4,3) d (5,3) e (3,3) c (2,2) f b (6,3) (1,1) h g (8,1) (7,1) 割点 : c b 桥 b bc 一个顶点 u 是割点, 当且仅当满足 (1) 或 (2) (1) u 为树根, 且 u 有多于一个子树 (2) u 不为树根, 且存在 (u,v) 为树枝边 ( 或称父子边, 即 u 为 v 在搜索树中的父亲 ), 使得 dfn(u)<=low(v) 非树枝边不可能是桥一条边 (u,v) 是桥, 当且仅当 (u,v) 为树枝边, 且满足 dfn(u)<low(v)( 前提是其没有重边 )

40 求桥和割点的 Trjn 算法 low[u] 定义为 u 或者 u 的子树中能够通过非父子边追溯到的最早的节点的 DFS 开始时间如果下面程序没有 : if(v 不是 u 的父节点 ) 则求不出桥了

41 求桥和割点和桥的 Trjn 算法 Trjn(u) { d[u]=low[u]=++index for ech (u, v) in E { if (v is not visted) trjn(v) low[u] = min(low[u], low[v]) d[u]<low[v] (u, v) 是桥 } else { if(v 不是 u 的父节点 ) low[u] = min(low[u], d[v]) } } if (u is root) u 是割点 <=> u 有至少两个子节点 else u 是割点 <=> u 有一个子节点 v, 满足 d[u]<= low[v] }

42 Trjn s lgorithm 也可以先用 Tjn() 进行 dfs 算出所有点的 low 和 dfn 值, 并记录 dfs 过程中每个点的父节点, 然后再把所有点看一遍, 看其 low 和 dfn, 以找出割点和桥找桥的时候, 要注意看有没有重边有重边, 则不是桥

43 无重边连通无向图求割点和桥的程序给出点数和所有的边, 求割点和桥 Input: (11 点 13 边 ) output: ,8 4,9 7,10

44 // 无重边连通无向图求割点和桥的程序 #include <iostrem> #include <vector> using nmespce std; #define MyMx 200 typedef vector<int> Edge; vector<edge> G(MyMx); bool Visited[MyMx] ; int dfn[mymx] ; int low[mymx] ; int Fther[MyMx]; //DFS 树中每个点的父节点 bool biscutvetext[mymx]; // 每个点是不是割点 int ntime; //Dfs 时间戳 int n,m; //n 是点数,m 是边数

45 void Trjn(int u, int fther) //fther 是 u 的父节点 { Fther[u] = fther; int i,j,k; low[u] = dfn[u] = ntime ++; for( i = 0;i < G[u].size() ;i ++ ) { int v = G[u][i]; if(! dfn[v]) { Trjn(v,u); low[u] = min(low[u],low[v]); } else if( fther!= v ) // 连到父节点的回边不考虑, 否则求不出桥 low[u] = min(low[u],dfn[v]); } }

46 void Count() { // 计算割点和桥 int nrootsons = 0; int i; Trjn(1,0); for( i = 2;i <= n;i ++ ) { int v = Fther[i]; if( v == 1 ) nrootsons ++; //DFS 树中根节点有几个子树 else { if( dfn[v] <= low[i]) biscutvetext[v] = true; } } if( nrootsons > 1) biscutvetext[1] = true; for( i = 1;i <= n;i ++ ) if( biscutvetext[i] ) cout << i << endl; for( i = 1;i <= n;i ++) { int v = Fther[i]; if(v >0 && dfn[v] < low[i]) cout << v << "," << i <<endl; } }

47 int min() { int u,v; int i; } ntime = 1; cin >> n >> m ; //n 是点数,m 是边数 for( i = 1;i <= m;i ++ ) { cin >> u >> v; // 点编号从 1 开始 G[v].push_bck(u); G[u].push_bck(v); } memset( dfn,0,sizeof(dfn)); memset( Fther,0,sizeof(Fther)); memset( biscutvetext,0,sizeof(biscutvetext)); Count(); return 0;

48 求无向图连通图点双连通分支 ( 不包含割点的极大连通子图 ): 对于点双连通分支, 实际上在求割点的过程中就能顺便把每个点双连通分支求出建立一个栈, 存储当前双连通分支, 在搜索图时, 每找到一条树枝边或反向边 ( 连到树中祖先的边 ), 就把这条边加入栈中如果遇到某树枝边 (u,v) 满足 dfn(u)<=low(v), 说明 u 是一个割点, 此时把边从栈顶一个个取出, 直到遇到了边 (u,v), 取出的这些边与其关联的点, 组成一个点双连通分支割点可以属于多个点双连通分支, 其余点和每条边只属于且属于一个点双连通分支

49 (1,1) d c b h g f e

50 d c (2,2) b (1,1) h g f e b

51 (2,2) b (3,3) c d (1,1) h g e f bc b

52 (2,2) b (3,3) c (4,4) d (1,1) h g e f cd bc b

53 (2,2) (1,1) (3,3) b g (4,4) d c h de (5,5) e f cd bc b

54 (2,2) (1,1) (3,3) b g (4,4) d c h ef (5,5) e f (6,6) de cd bc b

55 (2,2) (1,1) (3,3) b g (4,3) d c h fc ef (5,3) e f (6,3) de cd bc b 不要让 fc 入栈两次!

56 (3,3) (2,2) b (1,1) g 点双连通分量 : { fc,ef,de,cd } (4,3) d c h (6,3) (5,3) e f bc b

57 (2,2) b (3,3) c (4,3) d (1,1) h g 点双连通分量 : { fc,ef,de,cd } {bc } f (6,3) (5,3) e b

58 (2,2) b (3,3) c (4,3) d (1,1) h g 点双连通分量 : { fc,ef,de,cd } { bc } {b} f (6,3) (5,3) e

59 (2,2) b (3,3) c (4,3) d (1,1) h g (7,7) 点双连通分量 : { fc,ef,de,cd } { bc } {b} (6,3) (5,3) f g e

60 (2,2) b (3,3) c (4,3) d (1,1) g (7,7) h (8,8) 点双连通分量 : { fc,ef,de,cd } { bc } {b} (5,3) f (6,3) gh g e

61 (2,2) b (3,3) c (4,3) d (1,1) g (7,1) h (8,1) 点双连通分量 : { fc,ef,de,cd } { bc } {b} (5,3) f (6,3) h gh g e

62 (2,2) b (3,3) c (4,3) d (1,1) g (7,1) h (8,1) 点双连通分量 : { fc,ef,de,cd } { bc } {b} {h,gh,g} f (6,3) (5,3) e

63 求无向连通图点双连通分量 ( 没有割点的连通分量 ), 假定没有重边 Input: (11 点 13 边 ) output: Block No: 1 4,9 Block No: 2 4,1 3,4 3,2 11,3 2,11 1,2 Block No: 3 5,8 Block No: 4 7,10 Block No: 5 6,1 7,6 5,7 1,5

65 求无向连通图点双连通分量 ( 没有割点的连通分量 ), 假定没有重边 Input: (8 点 9 边 ) output: Block No: 1 7,4 8,7 6,8 4,6 Block No: 2 2,4 Block No: 3 1,2 Block No: 4 5,1 3,5 1,3

67 // 求无向连通图点双连通分量 ( 没有割点的连通分量 ), 假定没有重边 #include <iostrem> #include <vector> #include <queue> using nmespce std; #define MyMx 200 typedef vector<int> Edge; vector<edge> G(MyMx); int dfn[mymx] ; int low[mymx] ; int ntime; int n,m; //n 是点数,m 是边数 struct Edge2 { int u; int v; Edge2(int u_,int v_):u(u_),v(v_) { } }; deque<edge2> Edges; // 栈 int nblockno = 0;

68 void Trjn(int u, int fther) { int i,j,k; low[u] = dfn[u] = ntime ++; for( i = 0;i < G[u].size() ;i ++ ) { int v = G[u][i]; if(! dfn[v]) { //v 没有访问过 // 树边要入栈 Edges.push_bck(Edge2(u,v)); Trjn(v,u); low[u] = min(low[u],low[v]); Edge2 tmp(0,0); if(dfn[u] <= low[v]) { // 从一条边往下走, 走完后发现自己是割点, 则栈中的边一定全是和自己在一个双连通分量里面 // 根节点总是和其下的某些点在同一个双连通分量里面 cout << "Block No: " << ++ nblockno << endl;

69 do { tmp = Edges.bck(); Edges.pop_bck (); cout << tmp.u << "," << tmp.v << endl; }while (!(tmp.u == u && tmp.v == v) ); } } // 对应 if(! dfn[v]) { else { if( v!= fther ) {//u 连到父节点的回边不考虑 low[u] = min(low[u],dfn[v]); if( dfn[u] > dfn[v]) // 连接到祖先的回边要入栈, 但是连接到儿子的边, 此处肯定已经入过栈了, 不能再入栈 Edges.push_bck(Edge2(u,v)); } } } // 对应 for( i = 0;i < G[u].size() ;i ++ ) { }

70 int min() { } int u,v; int i; ntime = 1; cin >> n >> m ; //n 是点数,m 是边数 nblockno = 0; for( i = 1;i <= m;i ++ ) { cin >> u >> v; // 点编号从 1 开始 G[v].push_bck(u); G[u].push_bck(v); } memset( dfn,0,sizeof(dfn)); Trjn(1,0); return 0;

71 求无向连通图边双连通分支 ( 不包含桥的极大连通子图 ): 只需在求出所有的桥以后, 把桥边删除, 原图变成了多个连通块, 则每个连通块就是一个边双连通分支桥不属于任何一个边双连通分支, 其余的边和每个顶点都属于且只属于一个边双连通分支

72 POJ 3352 Rod Construction 给你一个图, 要求你加入最少的边, 使得最后得到的图为一个边双连通分支所谓的边双连通分支, 即不存在桥的连通分支可以求出所有的桥, 把桥删掉然后把所有的连通分支求出来, 显然这些连通分支就是原图中的双连通分支把它们缩成点, 然后添上刚才删去的桥, 就构成了一棵树在树上添边使得树变成一个双连通分支即可

73 POJ 3352 Rod Construction 本题只要求输出一共需要添加多少条边, 而不需要求具体的方案其实可以统计度为 1 的叶子节点 ( 设共有 x 个 ), 然后直接输出 (x+1)/2 即可

74 命题 : 一棵有 n(n>=2) 个叶子结点的树, 至少 ( 只需 ) 要添加 ceil(n/2) 条边, 才 ( 就 ) 能转变为一个没有桥的图或者说, 使得图中每条边, 都至少在一个环上证明 : 这里只证明 n 为偶数的情况 n 为奇数的证明类似先证明添加 n/2 条边一定可以达成目标 n=2 时, 显然只需将这两个叶子间连一条边即可命题成立设 n=2k(k>=1) 时命题成立, 即 AddNum(2k)=k 下面将推出 n=2(k+1) 时命题亦成立 n=2k+2 时, 选取树中一条迹 ( 无重复点的路径 ), 设其端点为,b; 并设离最近的度 >=3 的点为 ', 同理设 b' ( 关于和 b 的存在性问题 : 由于和 b 的度都为 1, 因此树中其它的树枝必然从迹 <,b> 之间的某些点引出否则整棵树就是迹 <,b>,n=2<2k+2, 不可能 )

75 b 不重合时 : 在,b 间添一条边, 则迹 <,b> 上的所有边都已不再是桥这时, 将刚才添加的边, 以及之间,bb 之间的边都删去, 得到一棵新的树因为删去的那些边都已经符合条件了, 所以在之后的构造中不需要考虑它们由于之前和 b 的度 >=3, 所以删除操作不会使他们变成叶子因此新的树必然比原树少了两个叶子,b, 共有 2k 个叶子由归纳知需要再加 k 条边因此对 n=2k+2 的树, 一共要添加 k+1 条边

76 b 重合时 : ' b' b

77 b 重合时 : ' b' b 将和一个非 b 的叶子节点 x 连上, 然后将环缩点至因为叶子节点是偶数, 所以必然还存在一个非 b 非 x 的叶子节点不在环上, 因此不会变成叶子节点, 于是新图比原图少 2 个叶子节点

78 再证明 n/2 是最小的解显然, 只有一个叶子结点被新加的边覆盖到, 才有可能使与它相接的那条边进入一个环中而一次加边至多覆盖 2 个叶子因此 n 个叶子至少要加 n/2 条边证毕

79 其他题目 cm1236,cm3180,cm2762( 强连通 + 拓扑排序 ),cm2553,cm3114( 强连通 +dijkstr), cm3160( 强连通 +DP)

Microsoft Word - 专升本练习5：图.doc

Microsoft Word - 专升本练习5：图.doc 第五章图一选择题 1. 关键路径是事件结点网络中的 ( ) A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 2. 一个具有 n 个顶点和 e 条边的无向图, 采用邻接表表示, 表向量的大小为 ( 1 ), 所有顶点邻接表的结点总数为 ( 2 ) 1A. n B. n+1 C. n-1 D. n+e 2A. e/2 B. e C. 2e D. n+e