这篇文章，搬运了此篇，但是MARKDOWN重修。建议还是看原本。搬运目的：为了宣传上述文章，帮助更多人。基本定义边导出子图：选出若干条边，以及这些边所连接的所有顶点组成的图称为边导出子图。点导出子图：选出若干个点，以及两端都在该点集的所有边组成的图称为点导出子图。闭合子图：定义在有向图上。点集V导出的闭合子图是所有V可达的点的点导出子图。其精确定义为若x在子图内，则x的所有出点和出边均在子图内的原图子图；等价于每个点能到的所有点都在子图中。1.最短路最短路是图论最基本的一类问题。下文记disu表示从源点到节点u的最短路，n为节点数|V|，m为边数|E|。1.1Bellman-FordBellm

图论各章考点二、树1、避圈法（克鲁斯克尔算法）2、破圈法3、Prim算法四、路径算法1、Dijkstra算法2、Floyd算法五、匹配1、匈牙利算法（最大权理想匹配（最小权权值取反））六、行遍性问题1、Fleury算法（欧拉巡回）2、Edmonds算法（最佳巡回）3、Christofides最小权匹配算法（最佳H圈）4、二边逐次修正法（最佳H圈）5、最佳H圈七、平面图1、可平面性算法二、树1、避圈法（克鲁斯克尔算法）2、破圈法3、Prim算法四、路径算法1、Dijkstra算法2、Floyd算法五、匹配1、匈牙利算法（最大权理想匹配（最小权权值取反））六、行遍性问题1、Fleury算法（欧拉巡

描述创建无向图类，存储结构使用邻接链表，提供操作：插入一条边，删除一条边，BFS，DFS。格式输入第一行四个整数n，m，s，t。n(10≤n≤10000010\leqn\leq10000010≤n≤100000)代表图中点的个数，m(10≤m≤20000010\leqm\leq20000010≤m≤200000)代表接下来共有m个操作，s代表起始点，t代表终点。接下来m行，每行代表一次插入或删除边的操作，操作格式为：0uv在点u和v之间增加一条边1uv删除点u和v之间的边输出第一行输出图中有多少个连通分量第二行输出所有连通子图中最小点的编号（升序），编号间用空格分隔第三行输出从s点开始的dfs

文章目录0x01TelephoneLinesPOJ-36620x02P1073[NOIP2009提高组]最优贸易0x03道路和航线BZOJ22000x04SortingItAllOutPOJ-1094topo0x05SightseeingtripPOJ-1734最小环问题0x06CowRelaysPOJ-3613S到E经过k条边的最短路0x07走廊泼水节（Kruskal）0x01TelephoneLinesPOJ-3662TelephoneLines题意：从1到N修一条电缆，有p对电线杆之间是可以连接的，电信公司可以提供k条电缆，其他的由John提供，求john提供的电缆的最长的那根的长度（r

给定一个n个点n条边的无向图，你需要求有多少种选择图上的一个点p和一条边(x,y)的方案，使得删去(x,y)后图变成一棵树，且这棵树以p为根时每个节点的儿子个数均不超过3。保证至少存在一种这样的方案。Input输入的第一行一个整数n（2≤n≤105）表示节点数，接下来n行每行两个整数x,y（1≤x,y≤n）描述图上的一条边。保证图中没有重边自环。Output输出一行一个正整数表示答案。Input6121314151623Output10解析：n个点n条边，所以该图就成一个环。只有将环中的一条边删去，该图才能变为一棵树。#includeusingnamespacestd;#defineintlo

目录题目：村村通并查集 题目：最小生成树kruskal算法prim算法        先引入问题：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。说白了就是将此图连通起来的最小代价。        对于一个有N个点的图，边一定是大于等于N-1条的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的有两种算法：prim和kruskal前者适合稠密图，后者适合稀疏图(不然炸你内存)    

一.Java查找算法之折半查找        相关知识:折半查找又叫作二分查找，是一种在有序数组中查找某一特定元素的搜索算法，使用二分可以极大地缩小我们搜索的时间复杂度第1关：折半查找（二分查找）1.任务描述本关任务：给定一个排好序的数组，然后输入另一个整数，判断该整数在数组中的什么位置，返回该整数第一次出现的位置（位置从0开始），否则返回-1。样例1:测试输入:n=6，nums=[-1,0,3,5,9,12]，T=9预期输出:4解释:9出现在nums中并且下标为4样例2:测试输入:n=6，nums=[-1,0,3,5,9,12],T=2预期输出:-1解释:2不存在nums中因此返回-12.思

目录预备知识模板1：无向图的桥模板2：无向图的割点模板3：有向图的强连通分量                讲之前先补充一下必要概念：预备知识无向图的【连通分量】：即极大联通子图，再加入一个节点就不再连通（对于非连通图一定两个以上的连通分量）无向图的【(割边或)桥】：即去掉该边，图就变成了两个连通子图无向图的【割点】：将该点和相关联的边去掉，图将变成两个及以上的子图注意：有割点不一定有桥，但是有桥一定有割点        无向图的【边双连通图】:无向图中不存在桥，即删除一条边后仍然连通(每两个点间有至少两条路径，且路径上的边互不重复)           无向图的【点双连通图】:无向图中不存在

目录今天知识点并查集统计集合元素个数和每个元素的信息并查集处理关系层次从而判断节点关系POJ1988        思路：POJ1182        思路：                        POJ1988有n个栈每个栈中有一个方块，现要执行n次操作。一种是移数，一种是计数移数M：把包含x的栈整体移动到y栈顶计数C：统计X方块下面的方块数输入：6M16C1M24M26C3C4        思路：我们不需要模拟，我们只需要等价即可，每次操作无非是把一个链表接到了另一个链表上，这完全可以用并查集实现。        设置fa数组表示集合号，cnt表示x号栈中的数量，d为x下方的数量

684.冗余连接题目：树可以看成是一个连通且无环的无向图。给定往一棵n个节点(节点值1～n)的树中添加一条边后的图。添加的边的两个顶点包含在1到n中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为n的二维数组edges，edges[i]=[ai,bi]表示图中在ai和bi之间存在一条边。请找出一条可以删去的边，删除后可使得剩余部分是一个有着n个节点的树。如果有多个答案，则返回数组edges中最后出现的那个。题目链接：684.冗余连接代码如下：修改join函数classSolution{publicint[]father;publicint[]findRedundantConnect