《10月25日上午曹文《图的相关算法》ppt课件.ppt》由会员分享，可在线阅读，更多相关《10月25日上午曹文《图的相关算法》ppt课件.ppt（118页珍藏版）》请在三一办公上搜索。
1、图论,图的基本概念,图的基本概念,二元组 G(V,E) 称为图(graph)。 V为结点(node)或顶点(vertex)集。 E为图中结点之间的边的集合。点，用数字0n-1表示点对 (u,v) 称为边(edge)或称弧(arc)对于边 (u,v)E-u和v邻接(adjacent)-e和u、v关联(incident)子图(subgraph): 边的子集和相关联的点集,图的基本概念,有向图：边都是单向(unidirectional)的, 因此边(u,v)是有序数对. 有时用弧(arc)专指有向边带权图：可以给边加权(weight), 成为带权图, 或加权图(weighted graph). 权通
2、常代表费用、距离等, 可以是正数, 也可以是负数稠密性：边和V(V-1)/2相比非常少的称为稀疏图(sparse graph), 它的补图为稠密图(dense graph),路径和圈,一条路径(path)是一个结点序列, 路上的相邻结点在图上是邻接的如果结点和边都不重复出现, 则称为简单路径(simple path). 如果除了起点和终点相同外没有重复顶点和边, 称为圈(cycle). 不相交路(disjoint path)表示除了起点和终点没有公共点的路径. 更严格地-任意点都不相同的叫严格不相交路(vertex-disjoint path)-同理定义边不相交(edge-disjoint p
3、ath)路注意: 汉语中圈和环经常混用(包括一些固定术语). 由于一般不讨论自环(self-loop), 所以以后假设二者等价而不会引起混淆,连通性,如果任意两点都有路径, 则称图是连通(connected)的, 否则称图是非连通的. 非连通图有多个连通分量(connected component, cc), 每个连通分量是一个极大连通子图(maximal connected subgraph),完全图和补图,完全图:N个顶点的无向图，有N(N-1)/2条边对于(u,v), 若邻接则改为非邻接, 若非邻接则改为邻接, 得到的图为原图的补图完全图=原图补图团：完全子图,生成树,树：N个点，N-1
4、条边的连通图（无环连通图）生成树: 包含某图G所有点的树一个图G是树当且仅当以下任意一个条件成立G有V-1条边, 无圈G有V-1条边, 连通任意两点只有唯一的简单路径G连通, 但任意删除一条边后不连通,图例,图的表示方法,介绍两种图的表示方法：邻接矩阵与邻接表V*V的二维数组A，Aij=0,若(i,j)不相连，Aij=1,若(i,j)相连,图1,图1的邻接矩阵表示,邻接矩阵,无向图的邻接矩阵是对称的优点：查找/删除某条边是O(1)的缺点遍历某一点的邻居是O(V)的空间复杂度很大，O(V*V),每个结点的邻居形成一个链表,邻接表,图2,图2的邻接表表示,优点快速遍历某点所有邻居占用存储空间小，是
5、O（边数）的，在稀疏图上的效率远胜邻接矩阵缺点：查找/删除边不是常数时间,邻接表,前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.用leni来记录所有以i为起点的边在数组中的存储长度.用headi记录以i为边集在数组中的第一个存储位置.,链式前向星,那么排完序后就得到:编号: 1 2 3 4 5 6 7起点u: 1 1 1 2 3 4 4终点v: 2 3 5 3 4 1 5head1 = 1 len1 = 3head2 = 4 len2 = 1hea
6、d3 = 5 len3 = 1head4 = 6 len4 = 2,链式前向星,但是利用前向星会有排序操作,如果用快排时间至少为O(nlog(n)如果用链式前向星,就可以避免排序.我们建立边结构体为：struct edgeint next,to,w;其中edgei.to表示第i条边的终点,edgei.next表示与第i条边同起点的下一条边的存储位置,edgei.w为边权值。另外还有一个数组headi,它是用来表示以i为起点的第一条边存储的位置，实际上你会发现它是以i为起点的所有边的最后输入的那个编号。head数组一般初始化为-1。,链式前向星,void add(int u,int v,int
7、w) edgecnt.w = w; edgecnt.to = v; edgecnt.next = headu; headu = cnt+; 我们在遍历以u节点为起始位置的所有边的时候是这样的: for(int i=headu;i;i=edgei.next),链式前向星,一、宽度优先遍历(BFS)二、深度优先遍历(DFS),图的遍历算法,给定图G和一个源点s, 宽度优先遍历按照从近到远的顺序考虑各条边. 算法求出从s到各点的距离宽度优先的过程对结点着色. 白色: 没有考虑过的点黑色: 已经完全考虑过的点灰色: 发现过, 但没有处理过, 是遍历边界依次处理每个灰色结点u, 对于邻接边(u, v),
8、 把v着成灰色并加入树中, 在树中u是v的父亲(parent)或称前驱(predecessor). 距离dv = du + 1整棵树的根为s,宽度优先遍历(BFS),题目大意： 给出N*M个格子，给出K个已经被淹没的格子，其他格子都是干的，求最大的湖的面积（一个格子的面积视为1），如果两个湿的格子四联通（上下左右），则视为这两个格子同属于一个湖输入格式： 第一行N，M，K 接下来K个格子的坐标,Avoid The Lakes （NOI题库2405）,Input3 4 5 3 2 2 2 3 1 2 3 1 1,Output4,样例解释#.#.#.,新发现的结点先扩展得到的可能不是一棵树而是森林
9、, 即深度优先森林(Depth-first forest)特别之处: 引入时间戳(timestamp)发现时间dv: 变灰的时间结束时间fv: 变黑的时间1=dv fv = 2|V|,深度优先遍历(DFS),初始化: time为0, 所有点为白色, dfs森林为空对每个白色点u执行一次DFS-VISIT(u)时间复杂度为O(n+m),深度优先遍历(DFS),括号结构性质对于任意结点对(u, v), 考虑区间du, fu和dv, fv, 以下三个性质恰有一个成立:完全分离u的区间完全包含在v的区间内, 则在dfs树上u是v的后代v的区间完全包含在u的区间内, 则在dfs树上v是u的后代,DFS树
10、的性质,定理(嵌套区间定理):在DFS森林中v是u的后代当且仅当dudvfvfu, 即区间包含关系. 由区间性质立即得到.,DFS树的性质,一条边(u, v)可以按如下规则分类树边(Tree Edges, T): v通过边(u, v)发现后向边(Back Edges, B): u是v的后代前向边(Forward Edges, F): v是u的后代交叉边(Cross Edges, C): 其他边，可以连接同一个DFS树中没有后代关系的两个结点, 也可以连接不同DFS树中的结点判断后代关系可以借助定理1,边的分类,当(u, v)第一次被遍历, 考虑v的颜色白色, (u,v)为T边灰色, (u,v)
11、为B边 (只有它的祖先是灰色)黑色: (u,v)为F边或C边. 此时需要进一步判断dudv: C边 (v早就被发现了, 为另一DFS树中)时间复杂度: O(n+m)定理: 无向图只有T边和B边 (易证),边分类算法,if (dv = -1) dfs(v); /树边, 递归遍历else if (fv = -1) show(“B”); /后向边else if (dv du) show(“F”); / 前向边else show(“C”); / 交叉边d和f数组的初值均为-1, 方便了判断,实现细节,DAG:有向无环图拓扑顺序：,拓扑排序算法,对图G使用DFS算法, 每次把一个结点变黑的同时加到链表首
12、部AN EXAMPLE定理1: 有向图是DAG当且仅当没有返祖边如果有返祖边, 有环(易证)如果有环c, 考虑其中第一个被发现的结点v, 环中v的上一个结点为u, 则沿环的路径vu是白色路径, u是v的后代, 因此(u, v)是返祖边定理2: 该算法正确的得到了一个拓扑顺序的逆序,拓扑排序算法,图的最短路问题,SSSP的 Spfa算法SSSP的 Dijkstra算法差分约束系统Floyd-warshall算法,给定带权图和一个起点s, 求s到所有点的最短路(边权和最小的路径)最短路有环吗正环: 何必呢, 删除环则得到更短路负环: 无最短路, 因为可以沿负环兜圈子,单源最短路问题(Single
13、Source Shortest Path),最优性原理: 若最短路uv经过中间结点w, 则uw和wv的路径分别是u到w和w到v的最短路意义: 贪心、动态规划,最优性原理,最短路的表示s到所有点的最短路不需要分别表示最短路树: 到每个点都沿着树上的唯一路径走实际代码: 记录每个点的父亲predu即可输出最短路: 从终点沿着predu递推回起点,最短路的表示,松弛（RELAX）操作一条边(u,v)被称为紧的(tense), 如果dist(u)+w(u,v)dist(v)可以松弛：dist(v)=dist(u)+w(u,v), pred(v)=u结论存在紧的边，一定没有正确的求出最短路树不存在紧的边
14、，一定正确的求出最短路树,SPFA算法,SPFA算法 伪代码,void SPFA() initialize-single-source(G,s); /初始化源点s以及其他点 initialize-queue(Q); /初始化队列 enqueue(Q,s); /源点s入队 while (!empty(Q)u=dequeue(Q); /取出队首元素 for (int v:adju) /遍历每个相邻的节点 tmp=dv; relax(u,v); /松弛操作 if (tmp!=dv) and (!v in Q) /判断是否要入队 enqueue(Q,v); /加入队尾 ,SPFA算法,优点：如其名，快
15、速。期望的时间复杂度：O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于4。有兴趣自己GOOGLE解决写起来很方便缺点：在网格图上的效率很低，接近O（n2）,POJ3259 - Wormholes,题目大意：虫洞问题，现在有n个点，m条边，代表现在可以走的通路，比如从a到b和从b到a需要花费c时间，现在在地上出现了w个虫洞，虫洞的意义就是你从a到b花费的时间是-c(时间倒流,并且虫洞是单向的)，现在问你从某个点开始走，能否回到从前,POJ3259 - Wormholes,提示：SPFA其实是Bellman-ford算法的优化而Bellman-ford可以用来判断一张图中是否存
16、在负环判断方法为：如果一个点被松弛了n次，那么图中就存在负环,POJ3259 - Wormholes,题解：按照题目意思建图，判断图中是否存在负环，存在即可回到过去。,把顶点集合V分成两组：（1）S：已求出的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定的顶点集合,Dijkstra算法（仅适用于无负权边的情况）,将T中顶点按递增的次序加入到S中，保证：（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点距离：从V0到此顶点的最短距离T中顶点距离：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度,Dijkstra
17、算法（仅适用于无负权边的情况）,正确性证明算法流程,Dijkstra算法,Dijkstra算法使用了一个优先队列INSERT (line 3), 每个结点一次EXTRACT-MIN, 每个结点一次DECREASE-KEY (line 8, 在RELAX过程中), 一共|E|次直接实现: O(V2)二项堆: O(ElogV)Fibonacci堆: O(E+VlogV),时间复杂度,在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件： 1路径上的所有点的出边所指向的点都直接或间接与终点连通。 2在满足条件1的情况下使路径最短。注意：图G中可能
18、存在重边和自环，题目保证终点没有出边。请你输出符合条件的路径的长度。,NOIP2014Day2T2寻找道路,输入格式：第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t,NOIP2014Day2T2寻找道路,Input 6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5Output 3,NOIP2014Day2T2寻找道路,如上图所示，满足条件的路径为1-3-4-5。注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不
19、与终点5连通。,大致思路：因为路径上的所有点的出边所指向的点都直接或间接与终点连通，所以我们不妨把所有的边反向，然后求t到s的最短路径大致证明：先将所有边按照读入顺序标号所有满足条件1的从s到t路径，在边都反向的情况下，对应一条t到s的路径，并且满足一一对应（因为路径上边的标号都相同）Tips：这里的最短路可以BFS求得（因为路径长度都是1）,NOIP2014Day2T2寻找道路,memset(f,true,sizeof(f); for (i=1;i=n;i+) for (j=pi;j;j=nextj) if (!hyj) fi=false; memset(d,127,sizeof(d); m
20、emset(h,false,sizeof(h); if (fs) ds=0;q0=s;hs=true; while (head=tail) for (i=pqhead;i;i=nexti) if (fyi) ,void travel(int t) ht=true; for (int i=pt;i;i=nexti) if (!hxi) travel(xi);int main() scanf(%d%d,线性规划(linear programming, LP): 给m*n矩阵A、m维向量b和n维向量c, 求出x为向量使得Ax=b, 且sumcixi最小可行性问题(feasibility proble
21、m): 只需要任意找出一组满足Ax=b的解向量x差分约束系统(system of difference constraints): A的每行恰好一个1和一个-1, 其他元素都是0. 相当于关于n个变量的m个差分约束, 每个约束都形如xj-xi=bk, 其中1=i,j=n, 1=k=m.,差分约束系统,左边的可行性问题等价于右边的差分约束系统,差分约束系统,约束图: 结点是变量, 一个约束对应一条弧, 若有弧(u, v), 则得到xu后, 有xv = xu + w(u,v),差分约束系统,定理: 如果约束图没有负圈, 则可取xu为起点v0到u的最短路长; 若约束图有负圈, 差分约束系统无解.正确
22、性证明无负圈: 由松弛条件可证明每个约束得到满足有负圈: 把负圈上的约束条件叠加将得到一个矛盾不等式算法步骤构图, 得到n+1个结点m+n条边运行最短路算法,差分约束系统,N个区间，ai,bi问一个整数的集合Z至少需要多少个元素，使得，在第i个区间的范围内至少有ci个整数属于集合Z。Sample Input Sample Output 6,Intervals POJ 1201,我们可以用xi表示集合中小于等于i的数的个数那么限制条件:ai,bi至少有ci个整数属于集合可以等价于xbi-xai-1=ci另外还有一个隐藏的条件：每个数只能出现一次：0=0，xi-1-xi=-1以上两个条件建立模型并
23、求最长路，便可得到答案,Intervals POJ 1201,void ins(int x,int y,int v) mp+s.y = y; mps.v = v; mps.next = firstx; firstx = s;int main() scanf(%d, ,dismx = 0; int head = 1,tail = 1; q1 = mx; vismx = 1; for (;head 0;t = mpt.next) int y = mpt.y; if (disx + mpt.v disy) disy = disx + mpt.v; if (not visy) visy = 1; ta
24、il+; qtail = y; visx = 0; printf(%dn,- dismn);,目标：给定图G，求出任意两点的最短路径动态规划的思想设di,j,k是在只允许经过结点1k的情况下i到j的最短路长度则它有两种情况（想一想，为什么）：最短路经过点k，dijk=dikk-1+dkjk-1最短路不经过点k，dijk=dijk-1,Floyd-warshall算法,编程复杂度低，三重循环注意：外层循环是K,Floyd-warshall算法,注意“无穷大”的运算时间复杂度: O(n3)空间复杂度: O(n2),Floyd-warshall算法,杭州有N个景区，景区之间有一些双向的路来连接，现在
25、8600想找一条旅游路线，这个路线从A点出发并且最后回到A点，假设经过的路线为V1,V2,.VK,V1,那么必须满足K2,就是说至除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。,HDU1599：find the mincost route,Input：第一行是2个整数N和M（N = 100, M = 1000)，代表景区的个数和道路的条数。接下来的M行里，每行包括3个整数a,b,c。代表a和b之间有一条通路，并且需要花费c元(c = 100)。Output：对于每个测试实例，如果能找到这样一条路线的话，输出花费
26、的最小值。如果找不到的话，输出“Its impossible.”。,HDU1599：find the mincost route,floyd求最小环:抛开Dijkstra算法，进而我们想到用Floyd算法。我们知道，Floyd算法在进行时会不断更新矩阵dist(k)。设distk，i，j表示从结点i到结点j且满足所有中间结点，它们均属于集合1，2， ，k的一条最短路径的权。其中dist0,i,j即为初始状态i到j的直接距离。当我们完成distk,i,j转移后，我们就能知道i到j不经过k及比k大的结点的最短路长度。,HDU1599：find the mincost route,回到问题上，满足题
27、目条件的一个环上（至少有3个点）有且只有一个编号最大的点，不妨设它为k，则这个环的长度可表示为:distk-1ij+wik+wjk，其中distkij表示i到j不经过k和比k大的结点的最短路长度，wik表示i结点与k结点的边权。,HDU1599：find the mincost route,K,i,j,wjk,distk-1ij,观察发现dist数组是Floyd算法中的中间结果，因此在进行Floyd的时候我们就可以顺带求出本题答案。 For(i,1,k-2)/枚举比k小的一个结点 For(j,i+1,k-1)/枚举比k小的另一个的结点 if (f0ikinf,HDU1599：find the
28、mincost route,但是万一所求的最小环中包含k+1，k+2， 怎么办？的确，如果最小环中包含比k大的节点，在当前所求出的环显然不是那个最小环。然而我们知道，这个最小环中必定有一个最大点k0，也就是说，虽然当前k没有求出我们所需要的最小环，但是当我们从k做到k0的时候，这个环上的所有点都小于k0了也就是说在k=k0时一定能求出这个最小环。同时，由于我们枚举k的两个直接相连的结点，因此算出的环至少有三个结点，满足题目要求。,HDU1599：find the mincost route,int main() int n,m;/init while (cinnm) For(i,0,n) Fo
29、r(j,1,n) For(k,1,n) if(j!=k) fijk=inf; For(i,1,m)/注意重边的判断! int from,to,dist; cinfromtodist; f0fromto=min(f0fromto,dist); f0tofrom=f0fromto; ,HDU1599：find the mincost route,int ans=inf;For(k,1,n) For(i,1,n)/floyd For(j,1,n) fkij=min(fk-1ij,fk-1ik + fk-1kj); For(i,1,k-2)/顺带统计答案 For(j,i+1,k-1) if (f0ik
30、inf ,最小生成树（MST,Minimal Spanning Tree）,PRIM算法并查集KRUSKAL算法,给定图G求连接每个点的连通图（一定是树）权和尽量小,最小生成树,假设选取若干条边，使得当前的图被分成了若干个连通分量无用边：边的两个端点属于同一个连通分量，但这条边不属于任意一个连通分量安全边：从它出去(即恰好有一个端点在此分量内)的最小边不同的分量可以有相同的安全边结论: MST含有所有安全边, 不含无用边.,最小生成树思想,结论: MST含有所有安全边, 不含无用边.证明假设有一个分量(黄色), 它的安全边e不在T内. 则u到v有唯一路径, 它经过e, 它恰好有一个端点在黄色分
31、量中. 由于e是安全边, w(e)w(e), 用e替换e得到更小的T, 矛盾加入无用边将形成环,最小生成树思想,只关心一棵树T, 每次加入T的安全边用堆保存到每个顶点(而非边)的安全边Insert/ExtractMin调用V次, DecreaseKey调用E次二叉堆: O(E+V)logV), Fibonacci堆: O(E+VlogV),PRIM算法,PRIM算法,将编号分别为1N的N个对象划分为不相交集合在每个集合中，选择其中某个元素代表所在集合常见两种操作：合并两个集合查找某元素属于哪个集合,并查集 Disjoint Set,每个集合用一棵“有根树”表示定义数组fa1.nfai=i，则i
32、表示本集合，并是集合对应树的树根fai=j, ji, 则 j 是 i 的父节点,并查集 Disjoint Set,查询x所在集合根节点合并集合a,b,并查集 Disjoint Set,find(x) while (fax != x) x = fax;return x;,最坏情况(log N),merge(a,b) if (height(a) = height(b) height(a) = height(a) + 1;fab = a; else if (height(a) height(b) faa = b;else fab = a; ,(1),思想：每次查找的时候，如果路径较长，则修改信息，以
33、便下次查找的时候速度更快步骤:第一步，找到根结点第二步，修改查找路径上的所有节点，将它们都指向根结点,路径压缩优化,find(x) while (x != fax) fax = find(fax);return fax;,路径压缩优化,Kruskal, 1956年提出把边从小到大排序, 每次添加一个安全边如何知道边是否安全? 并查集, 每次约O(1)总O(ElogE + E(V),Kruskal算法,A国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。输入文件第一
34、行有两个用一个空格隔开的整数n，m，表示A国有n座城市和m条道路。,NOIP2013Day1T3货车运输,接下来m行每行3个整数x、y、z，每两个整数之间用一个空格隔开，表示从x号城市到y号城市有一条限重为z的道路。 注意：x不等于y，两座城市之间可能有多条道路。 接下来一行有一个整数q，表示有q辆货车需要运货。 接下来q行，每行两个整数x、y，之间用一个空格隔开，表示一辆货车需要从x城市运输货物到y城市，注意：x不等于y。,NOIP2013Day1T3货车运输,输出共有q行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。Sample Input Sa
35、mple Output,NOIP2013Day1T3货车运输,4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3,3-13,大致思路：对于每个连通块，只保留这个连通块的最大生成树上的边然后对于每个询问，如果x，y联通，则输出x到y所经过的最大生成树上的边的最小值，否则输出-1对于如何求出这个最小值这需要用到倍增算法，有兴趣的同学可以课后自己去学习,NOIP2013Day1T3货车运输,你现在有一个集合，一开始集合为空，每次你会得到一对质数，如果集合中存在若干个数对，将这些数对和你得到的数对中所有的数乘起来是完全平方数，那么就将这个数对扔掉，否则就将这个数对加入集合。最后输出
36、扔掉的数的个数。（由于素数本身是什么并不重要，题中就只给出了素数的编号，编号相同的素数即为同一个素数）,Square dance（SPOJ131）,Square dance（SPOJ131）,Sample Input:6 71 2 3 5 2 4 1 4 3 5 1 64 6,Sample output:3,素数对数=100000素数的编号=100000,考虑怎样的一些数对才能够构成完全平方数，应该是每个数都出现了偶数次。如果把所有的数抽象成点呢？把数对抽象成边呢？那会构成一个什么呢？生成树！,Square dance（SPOJ131）,（1，2）（3，2）（3，1）,实际上题目冗长的描述仅仅
37、是讲了一棵生成树的生长过程。每次添加进来一个数对，实际上就是添一条边，然后如果这条边会与已有的边构成一条回路，则要扔掉这条边，否则就加入这条边，这与Kruskal算法惊人地相似！因此，我们只需要模拟一下Kruskal算法的实现流程，就能轻松地解决这一问题了。一个巧妙的变形，往往是解决问题的关键所在！,Square dance（SPOJ131）,给定一个N个点，M条边的图（N=20000，M=100000），边分为两种：实边和虚边。要求构造一棵生成树，使得正好包含K条虚边。如图便是N=5，M=7, K=2时的一组样例。,Road APIO 2008,先用实边跑生成树，然后剩下的连接各个连通块的虚
38、边是一定要选的。重置并查集，把必选的虚边都选上，因为那些连通块用实边就能联通，所以再随便加虚边也无所谓。加虚边到k条，剩下的再用实边做。无解就是必选的虚边大于k条或者无法补齐至k条,Road APIO 2008,一、有向图: SCC划分的Tarjan算法二、无向图: 割顶和桥的判定,强连通分量,一、有向图: SCC划分的Kosaraju算法(有兴趣的同学自己看吧)二、有向图: SCC划分的Tarjan算法三、无向图: 割顶和桥的判定,图的连通性算法,有向图中, u可达v不一定意味着v可达u. 相互可达则属于同一个强连通分量 (Strongly Connected Component, SCC)
39、有向图和它的转置的强连通分量相同所有SCC构成一个DAG,SCC的概念,Tarjan算法是基于对图深度优先搜索的算法每个强连通分量为搜索树中的一棵子树搜索时，把当前搜索树中未处理的节点加入一个堆栈回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。,tarjan算法(参考byvoid博客),定义：DFN(u)为节点u搜索的次序编号(时间戳)Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。,dfn与low函数,算法伪代码,tarjan(u) DFNu=Lowu=+Index / 为节点u设定次序编号和Low
40、初值 Stack.push(u) / 将节点u压入栈中 for each (u, v) in E / 枚举每一条边 if (v is not visted) / 如果节点v未被访问过 tarjan(v) / 继续向下找 Lowu = min(Lowu, Lowv) else if (v in S) / 如果节点v还在栈内 Lowu = min(Lowu, DFNv) if (DFNu = Lowu) / 如果节点u是强连通分量的根 repeat v = S.pop / 将v退栈，为该强连通分量中一个顶点 print v until (u= v),算法演示,算法演示,算法演示,算法演示,完整代码
41、,void tarjan(int i) int j; DFNi=LOWi=+Dindex; instacki=true; Stap+Stop=i; for (edge *e=Vi;e;e=e-next) j=e-t; if (!DFNj) tarjan(j); if (LOWjLOWi) LOWi=LOWj; else if (instackj ,if (DFNi=LOWi) Bcnt+; do j=StapStop-; instackj=false; Belongj=Bcnt; while (j!=i); void solve() int i; Stop=Bcnt=Dindex=0; mem
42、set(DFN,0,sizeof(DFN); for (i=1;i=N;i+) if (!DFNi) tarjan(i);,N头奶牛(N10000)M对关系（a , b），表示a认为b是受欢迎的关系具有传递性，即若(a,b),(b,c)(a,c)询问有多少头奶牛是被其他所有奶牛认为是受欢迎的,Popular Cows ( POJ2186 ),求出所有的强连通分量每个强连通分量缩成一点，则形成一个有向无环图DAG。DAG上面如果有唯一的出度为0的点，则该点能被所有的点可达。 那么该点所代表的连通分量上的所有的原图中的点，都能被原图中 的所有点可达 ，则该连通分量的点数就是答案。DAG上面如果有不
43、止一个出度为0的点，则这些点互相不可达，原问题无解，答案为0；,Popular Cows ( POJ2186 ),void Tarjan(int now) visnow = 0; lownow = dfnnow = +times; instacknow = 1; stack+top = now; for (int k = connnow;k;k = nextk) if (visak) Tarjan(ak,lownow = min(lownow,lowak); else if (instackak) lownow = min(lownow,dfnak); if (dfnnow = lownow)
44、 newnumnow = +num; instacknow = 0; sizenum = 1; while (stacktop != now) newnumstacktop = num; instackstacktop- = 0; +sizenum; -top; ,int main() scanf(%d%d,对于无向连通图G割顶是去掉以后让图不连通的点桥是去掉以后让图不连通的边,割顶与桥,lowu为u及其的后代所能追溯到的最早(最先被发现)祖先点v的dfnv值类似有向图的计算方式, 注意无向图只有T和B边lowu = dfnu = time+;for (u的不等于u的邻居v) / 不考虑自环
45、if (prev = -1) / 白色点 dfs-visit(v); if (lowu lowv) lowu = lowv; else if (lowu dfnv) lowu = dfnv; ,无向图的LOW函数,在一棵DFS树中根root是割顶当且仅当它至少有两个儿子其他点v是割顶当且仅当它有一个儿子u, 从u或者u的后代出发没有指向v祖先(不含v)的B边, 则删除v以后u和v的父亲不连通, 故为割顶割顶判定算法:对于DFS树根, 判断度数是否大于1对于其他点u, 如果不是根的直接儿子, 且lowu = dfnPu, 则它的父亲v=Pu是割点,割顶的判定,Network (POJ 1144)
46、,void dfs(int u,int dep) dfnu=lowu=dep; for (int i=0; i=dfnu) cutu=true; /由后继节点搜不到比该点更早的点，则该点是割点 else lowu=min(lowu,dfnv); ,题目大意：给定一个无向图，求有多少点是割点,边(u,v)为桥当且仅当它不在任何一个简单回路中发现T边(u,v)时若发现v和它的后代不存在一条连接u或其祖先的B边, 则删除(u,v)后u和v不连通, 因此(u,v)为桥桥的判定算法: 发现T边(u, v)时若LOWvdu(注意不能取等号), 则(u,v)为桥,桥的判定,Byteotia有n个镇。有的镇被
47、双向的道路连接。每一对镇间最多只有一条直接连接的道路。任意两个镇连通。每个镇刚好有一个市民。他们为孤独所困。每个居民都想看看其他所有居民（去他所在的地方），而且刚好做一次。所以刚好发生了n*(n-1)次访问。不幸的是，一些程序员正在罢工，为了使软件的销售量提高。作为抗议活动的一部分，程序员想把Byteotia的一条道路关闭，阻止通过这条道路。他们正在辩论选择哪一条道路会使得后果最严重。（后果最严重即删去这条道路后访问次数最少）,例题,例题,如图，若删去D,E之间的边，则会减少16次访问，若删去G,H之间的，会减少7次访问。若删除其它边，则不会减少访问次数。,应该删除哪些边？很显然，只有删除桥才
48、会减少访问次数，删去其它的边，图依然保持连通。因此，首先应该求出所有的桥。,例题,然后我们分别考虑每个桥的情况，删去这条边，会导致把图分成2个部分，而这两个部分是不连通的。考虑损失掉的访问，其实就是跨越这两个部分的访问，即|S1|*|S2|次访问，|S1|,|S2|是两个部分的大小。由此，大致的算法就形成了，枚举每一条边，然后计算损失的访问，最后输出答案即可。,例题,void tj(int x, int fa) lowx=dfnx=+tm, sizex=1; for (auto p:gx) if (p!=fa) if (!lowp) tj(p,x), sizex+=sizep; lowx=st
49、d:min(lowx,lowp); int main() int n,m,u,v; ll ans=0; scanf(%d%d,给定一张连通图G（V , E）(V=5,000，E=10,000)询问至少要添加多少条边，使得，任意两点间至少有2条路径可达？,Redundant Paths (POJ 3177),首先用tarjan求桥，桥把整张图分为了若干个双连通分量。之后将每个双连通分量缩为一个点，可以得到一棵树，问题转化为：在树上加边，使得整棵树没有桥。显然，所有的叶节点都需要连一条边。我们可以选择一个非叶节点为根，按照DFS序，将第i个叶节点与第i+n/2个相连。如果是奇数，则将中间一个与根相
50、连。,Redundant Paths (POJ 3177),void tarjan(int u) stack+top=u;instacku=true;fu=false; time+;lowu=time;dfnu=time; for(int i=headu;i;i=pi.next) v=pi.key; if(fv) fav=u; tarjan(v); lowu=min(lowu,lowv); else if(instackv) ,int main() cinnm;memset(head,0,sizeof(head); for(int i=1;ixiyi; p+cntp.key=yi;pcntp.
