下载文档原格式
初期:一.基本算法:(1)枚举. (poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026)(4)拓扑排序 (poj1094)(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)(6)最大流的增广路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)串 (poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)(3)简单并查集的应用.(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书 page149):1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)(4)凸包. (poj2187,poj1113)中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化 (poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等) (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题. (poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和高效性. poj3434二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解) (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446) (3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树.(6)无向图、有向图的最小环三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的).(poj2823)(4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点). (poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法.(poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划. (poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263) 以及补充Dp状态设计与方程总结1.不完全状态记录<1>青蛙过河问题<2>利用区间dp2.背包类问题<1> 0-1背包，经典问题<2>无限背包，经典问题<3>判定性背包问题<4>带附属关系的背包问题<5> + -1背包问题<6>双背包求最优值<7>构造三角形问题<8>带上下界限制的背包问题(012背包)3.线性的动态规划问题<1>积木游戏问题<2>决斗（判定性问题）<3>圆的最大多边形问题<4>统计单词个数问题<5>棋盘分割<6>日程安排问题<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)<8>方块消除游戏(某区间可以连续消去求最大效益)<9>资源分配问题<10>数字三角形问题<11>漂亮的打印<12>邮局问题与构造答案<13>最高积木问题<14>两段连续和最大<15>2次幂和问题<16>N个数的最大M段子段和<17>交叉最大数问题4.判定性问题的dp(如判定整除、判定可达性等)<1>模K问题的dp<2>特殊的模K问题，求最大(最小)模K的数<3>变换数问题5.单调性优化的动态规划<1>1-SUM问题<2>2-SUM问题<3>序列划分问题(单调队列优化)6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)<1>凸多边形的三角剖分问题<2>乘积最大问题<3>多边形游戏(多边形边上是操作符,顶点有权值)<4>石子合并(N^3/N^2/NLogN各种优化)7.贪心的动态规划<1>最优装载问题<2>部分背包问题<3>乘船问题<4>贪心策略<5>双机调度问题Johnson算法8.状态dp<1>牛仔射击问题(博弈类)<2>哈密顿路径的状态dp<3>两支点天平平衡问题<4>一个有向图的最接近二部图9.树型dp<1>完美服务器问题(每个节点有3种状态)<2>小胖守皇宫问题<3>网络收费问题<4>树中漫游问题<5>树上的博弈<6>树的最大独立集问题<7>树的最大平衡值问题<8>构造树的最小环转一个搞ACM需要的掌握的算法.要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红, 发挥自己的长处,这才是重要的.第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来.1.最短路(Floyd、Dijstra,BellmanFord)2.最小生成树(先写个prim,kruscal要用并查集，不好写)3.大数（高精度）加减乘除4.二分查找. (代码可在五行以内)5.叉乘、判线段相交、然后写个凸包.6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.8. 调用系统的qsort, 技巧很多，慢慢掌握.9. 任意进制间的转换第二阶段：练习复杂一点，但也较常用的算法。
图的割点、桥与双连通分支[点连通度与边连通度]在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。
一个图的点连通度的定义为，最小割点集合中的顶点数。
类似的，如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。
一个图的边连通度的定义为，最小割边集合中的边数。
注：以上定义的意思是，即有可能删除两个或两个以上点的时候才能形成多个连通块！[双连通图、割点与桥]如果一个无向连通图的点连通度大于1，则称该图是点双连通的(point biconnected)，简称双连通或重连通。
一个图有割点，当且仅当这个图的点连通度为1，则割点集合的唯一元素被称为割点(cut point)，又叫关节点(articulation point)。
如果一个无向连通图的边连通度大于1，则称该图是边双连通的(edge biconnected)，简称双连通或重连通。
一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥(bridge)，又叫关节边(articulation edge)。
可以看出，点双连通与边双连通都可以简称为双连通，它们之间是有着某种联系的，下文中提到的双连通，均既可指点双连通，又可指边双连通。
[双连通分支]在图G的所有子图G’中，如果G’是双连通的，则称G’为双连通子图。
如果一个双连通子图G’它不是任何一个双连通子图的真子集，则G’为极大双连通子图。
双连通分支(biconnected component)，或重连通分支，就是图的极大双连通子图。
特殊的，点双连通分支又叫做块。
[求割点与桥]该算法是R.Tarjan发明的。
对图深度优先搜索，定义DFS(u)为u在搜索树（以下简称为树）中被遍历到的次序号。
定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。
有向图的强连通分量分类：C/C++程序设计2009-04-15 16:50 2341人阅读评论(1) 收藏举报最关键通用部分：强连通分量一定是图的深搜树的一个子树。
一、Kosaraju算法1.算法思路基本思路：这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图G T。
(步骤1)先用对原图G进行深搜形成森林(树)，（步骤2）然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是E AB存在于反图G T)，能遍历到的顶点就是一个强连通分量。
余下部分和原来的森林一起组成一个新的森林，继续步骤2直到没有顶点为止。
7改进思路：当然，基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通分量只能存在单棵树中(由开篇第一句话可知))，我们当然不这么做，我们可以巧妙的选择第二深搜选择的树的顺序，使其不可能深搜到其他树上去。
想象一下，如果步骤2是从森林里选择树，那么哪个树是不连通(对于G T来说)到其他树上的呢？就是最后遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。
这给我们提供了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i]=j。
那么，我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于G T来说)就可以了。
每次深搜都得到一个强连通分量。
隐藏性质:分析到这里，我们已经知道怎么求强连通分量了。
但是，大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢？如果在看上述思路的时候，你的脑子在思考，相信你已经知道了！！！它就是：如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。
为什么呢？首先，应该明确搜索后的图一定是有向无环图呢？废话，如果还有环，那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量，而不是构成环上那么多点对应的独自的强连通分量了。
图论图论图论是数学的⼀个分⽀。
它以图为研究对象。
图论中的图是由若⼲给定的点及连接两点的线所构成的图形，这种图形通常⽤来描述某些事物之间的某种特定关系，⽤点代表事物，⽤连接两点的线表⽰相应两个事物间具有这种关系。
欧拉回路定义边权：离散数学或数据结构中，图的每条边上带的⼀个数值，它代表的含义可以是长度等等，这个值就是边权欧拉路径：如果图中的⼀个路径包括每个边恰好⼀次，则该路径称为欧拉路径。
欧拉回路：⾸尾相接的欧拉路径称为欧拉回路。
dfs（深度优先搜索）深度优先搜索是⼀种在开发爬⾍早期使⽤较多的⽅法。
它的⽬的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML⽂件) 。
在⼀个HTML⽂件中，当⼀个超链被选择后，被链接的HTML⽂件将执⾏深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的⼀条链。
深度优先搜索沿着HTML⽂件上的超链⾛到不能再深⼊为⽌，然后返回到某⼀个HTML⽂件，再继续选择该HTML⽂件中的其他超链。
当不再有其他超链可选择时，说明搜索已经结束。
判定由于每⼀条边都要经过恰好⼀次，因此对于除了起点和终点之外的任意⼀个节点，只要进来，⼀定要出去。
⼀个⽆向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数，且该图只有⼀个存在边的连通块。
⼀个⽆向图存在欧拉路径，当且仅当该图中奇点的数量为0或2，且该图只有⼀个存在边的连通块。
⼀个有向图存在欧拉回路，当且仅当所有点的⼊度等于出度。
⼀个混合图存在欧拉回路，当且仅当存在⼀个对所有⽆向边定向的⽅案，使得所有点的⼊度等于出度。
需要⽤⽹络流。
求法我们⽤ dfs（深度优先搜索）来求出⼀张图的欧拉回路。
我们给每⼀条边⼀个 vis数组代表是否访问过，接下来从⼀个点出发，遍历所有的边。
直接dfs并且记录的话会有⼀些问题。
为了解决这个问题，我们在记录答案的时候倒着记录，也就是当我们通过 (u, v) 这条边到达 v 的时候，先把 v dfs 完再加⼊ (v, u) 这条边。
图的割点、桥与双连通分支[点连通度与边连通度]在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。
一个图的点连通度的定义为，最小割点集合中的顶点数。
类似的，如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。
一个图的边连通度的定义为，最小割边集合中的边数。
[双连通图、割点与桥]如果一个无向连通图的点连通度大于1，则称该图是点双连通的(point biconnected)，简称双连通或重连通。
一个图有割点，当且仅当这个图的点连通度为1，则割点集合的唯一元素被称为割点(cut point)，又叫关节点(articulation point)。
如果一个无向连通图的边连通度大于1，则称该图是边双连通的(edge biconnected)，简称双连通或重连通。
一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥(bridge)，又叫关节边(articulation edge)。
可以看出，点双连通与边双连通都可以简称为双连通，它们之间是有着某种联系的，下文中提到的双连通，均既可指点双连通，又可指边双连通。
[双连通分支]在图G的所有子图G’中，如果G’是双连通的，则称G’为双连通子图。
如果一个双连通子图G’它不是任何一个双连通子图的真子集，则G’为极大双连通子图。
双连通分支(biconnected component)，或重连通分支，就是图的极大双连通子图。
特殊的，点双连通分支又叫做块。
[求割点与桥]该算法是R.Tarjan发明的。
对图深度优先搜索，定义DFS(u)为u在搜索树（以下简称为树）中被遍历到的次序号。
定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。
根据定义，则有：Low(u)=Min{DFS(u)DFS(v) (u,v)为后向边(返祖边) 等价于DFS(v)<DFS(u)且v不为u的父亲节点Low(v) (u,v)为树枝边(父子边)}一个顶点u是割点，当且仅当满足(1)或(2)(1) u为树根，且u有多于一个子树。
强连通分量的定义
强连通分量是图论中的一个概念，指的是在有向图中，若任意两个顶点都存在一条有向路径，则这个有向图就是强连通的。
而强连通分量则指的是有向图中的极大强连通子图，即在该子图中任意两个顶点都是强连通的，并且该子图不能再加入其他的顶点或边使其仍然保持强连通。
在实际应用中，强连通分量有着广泛的应用。
比如在电路设计中，可以将电路看作一个有向图，每个元件看作一个顶点，元件之间的电线则看作一条有向边。
那么在这个电路中，如果存在一个强连通分量，则说明这些元件可以构成一个独立的电路模块，可以方便地进行测试和维护。
此外，在社交网络分析、路网规划等领域，强连通分量也有着重要的应用。
在实际应用中，我们可以通过深度优先搜索（DFS）或者Tarjan算法来求解一个有向图的强连通分量。
具体来说，DFS 算法可以通过遍历有向图来寻找所有的强连通分量；而Tarjan 算法则是一种更高效的算法，可以在O(V+E)的时间复杂度内求解一个有向图的所有强连通分量。
总之，强连通分量是图论中一个重要的概念，在实际应用中有着广泛的应用。
通过深入学习和理解这个概念，我们可以更好地应用它来解决实际问题。
对于一个无向图G：
定义一：删除一个点v是指删除点v以及所有与点v关联的边。
定义二：删除一条边e是指删除这条边，但是保留e的两个顶点。
点割集：V是一些顶点的集合，如果删除V中的所有顶点之后，G不在连通，但是对于V的任何真子集V1，删除V1后G仍然连通，则称V是点割集。
割点：如果点割集里只有一个顶点，那么这个顶点叫做割点。
点连通度：最小的点割集的大小。
边割集：E是一些边的集合，如果删除E里的所有边之后G不在连通，但是对于E的任何真子集E1,删除E1之后G仍然连通，则称E是边割集。
桥：如果边割集里只有一条边，该边称为桥。
边连通度：最小的边割集的大小。
双连通：如果一个图没有割点，那么这个图称为2-连通的，或者双连通的。
一个图的极大双连通子图称为双连通分量。
注意是极大而不是最大，即意味双连通子图不一定只有一个。
连通图的割点、割边(桥)、块、缩点，有向图的强连通分量一、基本概念无向图割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。
块：没有割点的连通子图割边：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。
缩点：把没有割边的连通子图缩为一个点，此时满足任意两点间都有两条路径相互可达。
求块跟求缩点非常相似，很容易搞混，但本质上完全不同。
割点可以存在多个块中(假如存在k个块中)，最终该点与其他点形成k个块，对无割边的连通子图进行缩点后(假设为k个)，新图便变为一棵k个点由k-1条割边连接成的树，倘若其中有一条边不是割边，则它必可与其他割边形成一个环，而能继续进行缩点。
有割点的图不一定有割边，如：3是割点，分别与(1,2)和(4,5)形成两个无割点的块有割边的图也不定有割点,如：w(1,2)为割边，有向图强连通分量：有向图中任意两点相互可达的连通子图，其实也相当于无向图中的缩点二、算法无向图借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。
dfn[i]表示DFS过程中到达点i的时间，low[i]表示能通过其他边回到其祖先的最早时间。
low[i]=min(low[i],dfn[son[i]])设 v,u之间有边w(v,u)，从v->u：如果low[u]>=dfn[v],说明v的儿子u不能通过其他边到达v的祖先，此时如果拿掉v,则必定把v的祖先和v的儿子u，及它的子孙分开，于是v便是一个割点，v和它的子孙形成一个块。
如果low[u]>dfn[v]时，则说明u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果v,u之间有两条无向边，需要仍视为割边的话，则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去，从而第二条无向重边不会被遍历而导致low[u]==dfn[v] ,而在另外一些问题中，比如电线连接两台设备A,B 如果它们之间有两根电线，则应该视为是双连通的，因为任何一条电线出问题都不会破坏A和B之间的连通性，这个时候，我们可以用一个used[]数组标记边的id,DFS时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id号，在开始遍历v->u前检查它的id是否在上一次u->v 时被标记，这样如果两点之间有多条边时，每次遍历都只标记其中一条，还可以通过其他边回去，形成第二条新的路求割点的时候，维护一个栈st 每遍历到一个顶点v则把它放进去，对它的子孙u如果dfn[u]为0，则表示还没有遍历到则先DFS(u),之后再判断low[u]和dfn[v]，如果low[u]>=dfn[v],则把栈中从栈顶到v这一系列元素弹出，这些点与v 形成一个块，如果u的子孙x也是一个割点，这样做会不会错把它们和v，u放在一起形成一个块呢，这种情况是不会发生的，如果发现x是一个割点，则DFS 到x那一步后栈早就把属于x的子孙弹出来了，而只剩下v,u的子孙，它们之间不存在割点，否则在回溯到v之前也早就提前出栈了！画一个图照着代码模拟一下可以方便理解。
连通分量（tarjan算法）对于有向图中，连通分量叫强连通分量对于⽆向图中，连通分量叫双连通分量，⽽在双连通分量中，⼜分为点双连通和边双连通。
重点讨论双连通的情况：以割点区分连通情况的双连通叫做点双连通分量，以割边区分连通情况的双连通叫做边双连通分量。
⽐如这个图中：1 4| \ / \| \ / \| 2 5| / \ /| / \ /3 6如果要的到两个连通分量的话，我们只有以2节点为割点，将图分为点双连通。
我们便可以得到两个双连通分量(1,2,3)、(2,4,5,6)。
再⽐如这个图：1 5| \ / \| \ / \| 2 — 4 6| / \ /| / \ /3 7如果要得到两个连通分量的话，我们只能以(2,4)边为割边，得到两个边双连通分量。
具体是将⼀个⽆向图分成点双连通还是边双连通得看具体的问题。
下⾯具体讨论⼀下⽤tarjan算法实现起来的区别。
1、对于边双连通分量，由于是以边为连通间的区分，那么每个点只属于⼀个连通分量，我们在深度遍历的时候，只需要记录某⼀点是否被访问即可。
2、但是对于点双连通分量，由上图也可以看出，2节点同时属于两个连通分量，如果还是以节点为重判对象的话，将得到错误的答案。
此时，我们应该以边为重判对象，⽽该边的两个端点，都同属于⼀个点双连通。
对于边双连通的实现，由于没有节点会重复属于两个以上的连通分量，所以我们可以先简单的遍历⼀遍整个图的tarjan标号(low、dnf)。
之后再进⾏⼀次深度遍历，以low[v]>dnf[u]为换⾊标准染⾊，最后每种颜⾊即⼀个分量。
代码：void tarjan(int u,int f) //f为⽗节点{low[u]=dnf[u]=++count;visit[u]=1;S.push(u);for(node *p=link[u];p;p=p->next){if(p->v==f)continue;if(!visit[p->v]) //⼀节点为重判对象{tarjan(p->v,u);if(low[u]>low[p->v]){low[u]=low[p->v];}}else if(low[u]>dnf[p->v])low[u]=dnf[p->v];}}void set_color(int u){for(node *p=link[u];p;p=p->next){if(!color[p->v]){if(low[p->v]>dnf[u]) //找到了关键割边，换⼀种颜⾊染⾊color[p->v]=++cut;elsecolor[p->v]=color[u]; //保持原来的颜⾊set_color(p->v);}}}对于点双连通的实现，经过上⾯的分析，由于存在点既属于A分量⼜属于B分量，所有我们此时采纳边为重判对象，⽽该边的两端点同属于⼀个分量代码：void col(int u){int x;node *p;++cut;do{p=stack[--top];color[p->v]=color[p->op->v]=cut;}while(p->op->v!=u);}void tarjan(int u){low[u]=dnf[u]=++cut;for(node *p=link[u];p;p=p->next){if(p->vist) //该边已被访问continue;p->vist=p->op->vist=1; //两个⽅向都标记已访问stack[top++]=p; //该边进栈if(!dnf[p->v]){tarjan(p->v);if(low[u]>low[p->v])low[u]=low[p->v];if(low[p->v]>=dnf[u]) //找到了关键割点col(u);}else if(low[u]>dnf[p->v])low[u]=dnf[p->v];}}。
信息学竞赛中的的割点与桥信息学竞赛中的割点与桥在信息学竞赛中，割点与桥是一种常见的图论概念。
它们是指在图中的某些节点或边被移除后，会导致图分割成不连通的部分。
本文将介绍割点与桥的概念、作用以及与竞赛题目的联系。
一、割点割点（Cut Vertex）是指在一个无向连通图中，如果删除某个节点后，整个图变得不再连通，那么该节点就被称为割点。
割点在信息学竞赛中具有重要的作用。
在解决一些与连通性相关的问题时，我们可以通过识别割点来判断图的连通性以及最小生成树的构建等。
举个例子，当我们需要在一幅图中找到从起点到终点的所有路径时，我们可以使用深度优先搜索算法，其中割点的作用就显现出来。
每当我们遍历到一个割点时，我们可以将该节点作为新的起点，继续搜索剩余的路径，从而找到更多的路径。
二、桥桥（Bridge），也被称为割边或者关节点。
在一个无向连通图中，如果删除某条边后，整个图变得不再连通，那么该边就被称为桥。
桥在信息学竞赛中的应用也非常广泛。
例如，在某些网络问题中，我们需要找出网络中最脆弱的连接，即最容易引起网络断裂的边。
这时，我们可以利用桥的概念来解决。
通过识别桥，我们可以找到那些关键的边，从而进行网络优化和故障排除。
三、割点与桥的联系割点和桥在信息学竞赛中通常是联系在一起的。
它们都具有判断连通性的作用，且在解决问题时都是通过删除节点或边来分割图。
在某些题目中，割点和桥的出现往往需要我们找到一些特殊的节点或边，以便达到题目要求。
充分理解割点和桥的概念，我们可以通过构建图模型和运用一些算法，如深度优先搜索或者并查集等，来解决这类问题。
总结：在信息学竞赛中，割点与桥是图论中的重要概念。
它们在判断连通性、最小生成树构建、网络优化等问题中起着关键的作用。
了解割点和桥的定义和应用，对于解决图论相关的竞赛题目将会非常有帮助。
因此，在备战信息学竞赛时，我们应该充分掌握割点与桥的概念和相关算法，并在实际题目中灵活运用。
这样才能更好地应对竞赛中的图论难题。
连通图的割点、割边(桥)、块、缩点，有向图的强连通分量一、基本概念无向图割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。
块：没有割点的连通子图割边：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。
缩点：把没有割边的连通子图缩为一个点，此时满足任意两点间都有两条路径相互可达。
求块跟求缩点非常相似，很容易搞混，但本质上完全不同。
割点可以存在多个块中(假如存在k个块中)，最终该点与其他点形成k个块，对无割边的连通子图进行缩点后(假设为k个)，新图便变为一棵k个点由k-1条割边连接成的树，倘若其中有一条边不是割边，则它必可与其他割边形成一个环，而能继续进行缩点。
有割点的图不一定有割边，如：3是割点，分别与(1,2)和(4,5)形成两个无割点的块有割边的图也不定有割点,如：w(1,2)为割边，有向图强连通分量：有向图中任意两点相互可达的连通子图，其实也相当于无向图中的缩点二、算法无向图借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。
dfn[i]表示DFS过程中到达点i的时间，low[i]表示能通过其他边回到其祖先的最早时间。
low[i]=min(low[i],dfn[son[i]])设 v,u之间有边w(v,u)，从v->u：如果low[u]>=dfn[v],说明v的儿子u不能通过其他边到达v的祖先，此时如果拿掉v,则必定把v的祖先和v的儿子u，及它的子孙分开，于是v便是一个割点，v和它的子孙形成一个块。
如果low[u]>dfn[v]时，则说明u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果v,u之间有两条无向边，需要仍视为割边的话，则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去，从而第二条无向重边不会被遍历而导致low[u]==dfn[v] ,而在另外一些问题中，比如电线连接两台设备A,B 如果它们之间有两根电线，则应该视为是双连通的，因为任何一条电线出问题都不会破坏A和B之间的连通性，这个时候，我们可以用一个used[]数组标记边的id,DFS时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id号，在开始遍历v->u前检查它的id是否在上一次u->v 时被标记，这样如果两点之间有多条边时，每次遍历都只标记其中一条，还可以通过其他边回去，形成第二条新的路求割点的时候，维护一个栈st 每遍历到一个顶点v则把它放进去，对它的子孙u如果dfn[u]为0，则表示还没有遍历到则先DFS(u),之后再判断low[u]和dfn[v]，如果low[u]>=dfn[v],则把栈中从栈顶到v这一系列元素弹出，这些点与v 形成一个块，如果u的子孙x也是一个割点，这样做会不会错把它们和v，u放在一起形成一个块呢，这种情况是不会发生的，如果发现x是一个割点，则DFS 到x那一步后栈早就把属于x的子孙弹出来了，而只剩下v,u的子孙，它们之间不存在割点，否则在回溯到v之前也早就提前出栈了！画一个图照着代码模拟一下可以方便理解。
求割边也是一样的。
有向图有向图强连通分量的算法有两个，一个是Kosaraju,另一个是Tarjan，前者需要两次DFS，代码量偏大但容易理解，后者只需要一次DFS和维护一个栈便可以，实现简单，详见这里>>强连通分量 Kosaraju PK Tarjan2010-04-22 16:23Kosaraju算法对每个不在树中的点开始DFS一次，并记录离开各点的时间，这里是离开的时间，而不是到达时的，比如有图1->2 2->3 则1,2,3分别对应的时间是3 2 1,因为3没有出边，所以最先离开，其次是2,最后是1,DFS后，在同一棵树中的点，如果dfn[v]>dfn[u]则说明点从v有可能到达u,而这棵树中的dfn[]最大的点，肯定可以到达每个点，从而在原图的逆图中，每次都选没有访问过的最大的dfn值开始DFS,如果可达点x 则说明它们是强连通的void DFS_T(int u){int i,v;if(used[u])return ;used[u]=1;id[u]=scc;for(i=q[u];i!=-1;i=Tedge[i].pre){v=Tedge[i].d;if(!used[v])DFS_T(v);}}void DFS(int v){int i,u;if(used[v])return ;used[v]=1;for(i=p[v];i!=-1;i=edge[i].pre){u=edge[i].d;if(!used[u])DFS(u);}order[++num]=v;}int Kosaraju(){int i,j,k,v,u;memset(used,0,sizeof(used));num=0;for(i=1;i<=n;++i)if(!used[i])DFS(i);memset(used,0,sizeof(used));memset(id,0,sizeof(id));scc=0;for(i=num;i>=1;--i)if(!used[order[i]])scc++,DFS_T(order[i]);}Tarjan算法dfn[v]记录到达点v的时间，跟上面的离开不同，low[v]表示通过它的子结点可以到达的所有点中时间最小值，即low[i]=min(low[i],low[u]),u为v的了孙，初始化时low[v]=dfn[u]。
如果low[v]比dfn[v]小，说明v可以通过它的子结点u,u1,u2...到达它的祖先v',则存在环，这个环上所有的点组成的子图便是一个强连通分量。
换一个角度看，如果当low[v]==dfn[v]时，则它的子树中所有low[u]==dfn[v]的点都与v构成一个环，维护一个栈，DFS过程中，每遍历一个点则把它放入栈中，当发现low[v]==dfn[v]则依次把栈里的元素都弹出来，当栈顶元素为v时结束，这些点便构成一个以v为树根的强连通分量。
仍以上图为例，首先遍历点1,并dfn[1]=low[1]=++num, num表示按先后访问时间编号 ,同时1入栈a.从3深入 dfn[3]=low[3]=2; 3入栈b.从3到5 dfn[5]=low[5]=3; 5入栈c.从5到6 dfn[6]=low[6]=4; 6入栈d.发现6没有子结点可走，这时判断dfn[6]==low[6],于是开始弹栈，当遇到6时则break,即共弹出一个元素，于是6便是一个强连通分量e.回溯至5,同样判断和弹栈，发现5也是一个强连通分量f.再回溯至3,发现有边3->4，dfn[4]=low[4]=5,4入栈g.4有边到1,由于1已经在栈里面，所以用dfn[1]更新low[4] 即low[4]=min(low[4],dfn[1])=1h.回溯更新4的父亲3的low值 low[3]=min(low[3],low[4])=1i.再回溯至1,发现有边1->2 继续深度遍历，2入栈,发现它的子结点4已经在栈中，直接更新low[2]=min(low[2],dfn[4]);j.回溯至1,从而1所有出发的边都走了一遍，这时再比较low[1]与dfn[1]，发现相等，于是开始弹栈，找到2,4,3,1这四个元素，构成一个连通分量。
void Tarjan(int v){dfn[v]=low[v]=++num;used[v]=1;st[++numSt]=v;for(int i=p[v];i!=-1;i=edge[i].pre){int u(edge[i].d);if(!dfn[u])//还没有标号的点{Tarjan(u);//先遍历它的子结点GetMin(low[v],low[u]);//用子结点更新当前点的low值}else if(used[u]&&GetMin(low[v],dfn[u]));}if(dfn[v]==low[v]){scc++;while(1){int u(st[numSt--]);id[u]=scc;used[u]=0;if(v==u)break;}}}int main(){for(int i=1;i<=n;++i)if(!dfn[i])Tarjan(i);}这里有一个疑问，为什么当发现一个点v的子结点u已经在栈中时用dfn[u]来更新low[v],而不是用low[u],感觉好象两个都可以用，因为只要保证low[v]尽可能变小就行了，三、代码实现割点和块求割点的时候由于不知道最开始选的树根是不是只有一个儿子，这样在DFS过来中不会满足low[u]>=dfn[v]而判为割点，但有两个或两个以上儿子的根肯定也是一个割点，所以要特判！void CutBlock(int v){dfn[v]=low[v]=++cnt;st[++top]=v;for(int i=p[v];i!=-1;i=edge[i].pre){int u(edge[i].d);if(dfn[u]==0){CutBlock(u);GetMin(low[v],low[u]);if(low[u]>=dfn[v]){ //V是一个割点block[0]=0;while (true) {block[++block[0]]=st[top];if (st[top--] == u) //只能弹到u为止，v还可以在其他块中break;}block[++block[0]]=v;//割点属于多个块，一定要补进去Count(block);}}else GetMin(low[v],dfn[u]);}}割边和缩点void CutEdge(int v,int fa){dfn[v]=low[v]=++cnt;st[++top]=v;for(int i=p[v];i!=-1;i=edge[i].pre){int u(edge[i].d);if(u==fa)continue;if(!dfn[u]){CutEdge(u,v);GetMin(low[v],low[u]);if(low[u]>dfn[v]){//边v->u为一条割边cutE[++numE]=E(v,u);// 将u及与它形成的连通分量的所有点存起来++numB;while(1){id[st[top]]=numB;if(st[top--]==u)break;}}}else GetMin(low[v],dfn[u]);}}有向图强连通分量void Tarjan(int v){dfn[v]=low[v]=++num;used[v]=1;st[++numSt]=v;for(int i=p[v];i!=-1;i=edge[i].pre){int u(edge[i].d);if(!dfn[u])//还没有标号的点{Tarjan(u);//先遍历它的子结点GetMin(low[v],low[u]);//用子结点更新当前点的low值 }else if(used[u]&&GetMin(low[v],dfn[u]));}if(dfn[v]==low[v]){scc++;while(1){int u(st[numSt--]);id[u]=scc;used[u]=0;if(v==u)break;}}}这里需要注意一个地方，上面标记为紫色的那行代码，相比上面两个代码，这里加了一个used[]判断点是否在栈中，为什么前面的不要，而这里需要呢，举个例子根据dfn可以看出搜索的顺序是1->2->5->6形成一个强连通分量(2,5,6)，于是开始退栈,回溯到1从3出发到达4,此时如果直接用dfn[2]更新low[4]的话，会得到low[4]=2,变小后而与dfn[4]不再相等，不能退栈，这与最后的4形成一个单独强连通分量是不符合的，所以，不在栈中的点，不能用来更新当前点的low[]值，为什么无向图不用标记呢，那时因为，边是无向的，有边从4->2同时也必有边2->4由于2之前被标记过，而遍历到当前结点4又不是通过w(2,4)这条边过来的，则必还存在另一条路径可以使2和4是相通的，(即图中的4-3-1-2),从而2,4是双连通的。
