如果一张无向图的N个节点N≥2可以分成AB两个非空集合，其中A∩B∅,并且在同一集合内的点都没有边相连，那么成这张无向图为一张二分图。

给定一张无向图，若存在一条从节点S到节点T的路径，恰好不重不漏地经过每条边一次(可以重复经过图中的节点)，则称该路径为S到T的欧拉路。特别地，若存在一条从节点S出发地路径，恰好不重不漏地经过每条边一次(可以重复经过图中的节点)，最终回到起点S,则称该路径为欧拉回路，存在欧拉回路的无向图被称为欧拉图。一、无向图1 存在欧拉路径的充要条件 : 度数为奇数的点只能有0或2个2 存在欧拉回路的充要条件 :

Quick-Union算法并查集的作用：解决连通性问题（连通性问题：对于集合中的点，进行连通以及查询的过程）Quick-Find算法基于染色的思想，处于相同连通集合的点，染成相同的颜色。合并操作：时间复杂度O(n)，将一个连通子集中的点的染色全部染成另一个连通子集的颜色。查询操作：时间复杂度O(1)，只需要判断该点的颜色。由于合并操作时间复杂度较高，故Quick-Find算法并不作为常用的并查集算

单源最短路径问题(Single Source ShortestPath,SSSP问题)是说，给定一张有向图GVEV是点集，E是边集，∣V∣n∣E∣m，节点以1n之间的连续整数编号，xyz描述一条从x出发，到达y，长度为z的有向边。设1号点为起点，求长度为n的数组dist，其中disti表示从起点1到节点i的最短路径的长度。

对于分量中任意两点u,v 必然可以从u走到v 且从v走到u:极大连通分量有向图的强连通分量无非是以下两种情况：1.绿色：存在后向边指向祖先结点2.红色：存在横插边指向的点有指向这两个点公共祖先节点从实际应用的角度来说，我们在求完强连通分量之后会进行缩点的操作。缩点之后，该图就变成了有向无环图(拓扑图)了，这样处理起来就会很方便。

给定无向图GVE若对于x∈V,从图中删去节点x以及所有与x关联的边后，G分裂成两个不连通的子图，则称x是G的。若对于e∈E,从图中删去边e之后，G分裂成两个不相连的子图，则称e为G的桥或。无向边xy是桥，当且仅当搜索树上存在x的一个子节点ydfnxlowy在无向图中不存在横插边，所以说如果满足以上条件，要么说明以y为根的子树只存在树边，要么说明下图中存在类似于红色这样的后向边，即无法通过其他路径到

图G中存在一个回路，该回路边权之和为负数，称之为负环。:统计每个点入队次数, 如果某个点入队n次, 说明存在负环。证明：一个点入队n次，即被更新了n次。一个点每次被更新时所对应最短路的边数一定是递增的，也正因此该点被更新n次那么该点对应的的最短路长度一定大于等于n，即路径上点的个数至少为n+1。根据抽屉原理，路径中至少有一个顶点出现两次, 也就是路径中存在环路。而算法保证只有距离减少才会更新, 所

我们把边权大于x的边权置为1，小于等于x的边权置为0，这样一来图就是一个只有0，1边权的图，我们可以求出一条从1到n的最短路径，如果路径长度。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。怎样走，才需要最少的时间？2.对于答案右边的区间，x变大了，大于x的边数就会减小，即大于x的边数小于k，同样满足

本题可以用区间DP来做的关键点在于，中序遍历的顺序就是树上每一个点投影的顺序，也正因此对于给定中序遍历序列的每一个区间，都能对应原树上的一棵完整的子树。本题和上一题的区别就是本题是环形，考虑枚举链中每一个断开的位置，一共有。最外层枚举长度，第二次枚举开始位置，第三次枚举k的位置，时间复杂度为。右边的区域，再把合并之后的两个能力石进行合并，因为将能量石。集合：将区间[i,j]内的石子合并在一起的方案

贪心算法（greedy algorithm，又称贪婪算法）是指：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，