在这篇博客中,我将简单地介绍许多函数式编程语言中一个重要的,也是独特的特性:Laziness。 a first taste of Laziness 所以,什么是Laziness呢?Laziness有一个更加正式的名称:lazy evaluation,也即 惰性求值 。简单来说,惰性求值意味着,表达式的值不会被立即求出,只有当需要的时候才会对其进行求值。 比如,下面的代码在运行时并不会报错,而可以安全地求出列表的长度。 length [error "Hey!", error "Here …

2020年02月19日 0条评论 148点热度 0人点赞 阅读全文

定义 二分图 又称作二部图,是图论中的一种特殊模型。 设 ((G=(V,E))) 是一个无向图,如果顶点(V)可分割为两个互不相交的子集((U,V)),并且图中的每条边((i,j))所关联的两个顶点(i)和(j)分别属于这两个不同的顶点集,则称图(G)为一个二分图。 一个无向图为二分图的充要条件是没有奇环。 二分图染色 求解算法 思路 判定一个图是否为二分图,使用dfs进行黑白染色,判定能否满足每条边的两个顶点异色。 实现 #include <cstdio> #include <cstring&g…

2020年02月12日 0条评论 342点热度 0人点赞 阅读全文

提出背景 在图论问题中,我们经常性遇到一些关于两个点是否连通的问题。 比如在最小生成树kruskal算法中,我们在逐渐选取最小边的时候,我们需要判断当前要选的边的两个顶点是否已经在同一连通块中。 有基础的同学都知道,在大多数图论问题中,我们的图都是通过邻接表或点对表示边而非邻接矩阵存储的,这样能够提高遍历和存储的时间和空间效率。但实际上,这两种方式也有一个严重的缺陷:不方便查询、修改指定的两点u和v的关系。于是在这种情况下的这两种方式构成的图的连通性也非常难以判断。 这时我们需要一种数据结构能够方便的维护查询图的连…

2020年02月12日 0条评论 271点热度 0人点赞 阅读全文