一只橘橘猫

图论

coderforces(20) dp动态规划(3) icpc(8) KMP算法(3) leetcode(1) STL(1) 人工智能(2) 优先队列(1) 字符串(5) 搜索(2) 数学(4) 日记(1) 最短路(3) 未归档(29) 杭电多校(7) 牛客多校(11) 牛客寒假训练营2020(6) 牛客练习赛(8) 线段树树状数组(2) 贪心(4) 题解(25)

/ 注册

全部文章 / 图论（共3篇）

二分图（最大匹配，最小覆盖数，最大独立集合）来自专栏

二分图定义：设G=(V, E)是一个无向图，如果顶点V可分割为两个互不相交的子集（A , B），且图中的每条边（i, j）所关联的两个定点分别属于这两个不同的顶点集，则称图G为一个二分图。性质：定理：当且仅当无向图G的每一个环的结点数均是偶数时，图G才是一个二分图。如果无环，相当于每的结点数...

2020-04-02

1 2408

最近公共祖先（LCA）来自专栏

学习算法——最近公共祖先算法介绍：LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科例题：洛谷-LCA模板题模板代码： #include <bits/stdc++.h> ...

2020-04-01

2 743

最小生成树 Kruskal和Prim算法

算法过程： 1.将图中所有的边按照权值进行排序。 2.将图中的每一条边进行遍历，找出权值最小的边（注意：不能与已经加入到最小生成树集合的边构成环），如果符合要求，则把该边加入到最小生成树的集合中。 3.重复步骤2，添加一个计数器，直到边的数量为n-1的时候跳出循环，算法结束。 #inclu...

最小生成树 kruskal prim

2019-08-31

0 531