昵称很长很长真是太好了

数据结构

bfs(5) codeforces(19) kmp(1) python(7) 前缀和(1) 图论(2) 未归档(14) 每日一题(14) 牛客(3) 线段树(4) 记忆优化搜索(1) 逆元(1) 题解(99)

/ 注册

全部文章 / 数据结构（共18篇）

图论-无向图的连通性(POJ1144)(POJ3352) 来自专栏

1.割点和割边：割点：在无向图中，删除某个节点后，图的连通分量数量增加，则称该节点为割点桥：如果删除某条边后，连通图变得不再连通，则此条边为桥，或者为割边下面说一种用DFS求割点的算法，即利用了“深度优先搜索生成树”求割点。如何判断一个点是否为割点呢？（1）如果这个点为搜索出发的点（根节点...

2020-05-28

0 1012

图论-有向图的连通性模板题（hdu1296）（hdu1827）来自专栏

1.强连通分量：强连通分量可以理解为边数最少的情况下是一个环。这里写了一个模板题用的是tarjan算法，当然还有其他算法。 tarjan算法的关键其实还是对于num数组和low数组的使用然后可以用栈来分离不同的ssc 感觉跟双边连通分量有异曲同工之妙第一题hdu1296 #pragma ...

2020-05-28

0 753

图论刷水题记录（一）（最短路-----dijkstra算法）来自专栏

最近实在不知道干些什么，感觉自己除了水题什么都不会做，算了去刷一刷图论的水题吧本来想合起来一起发，想了想太长的话以后看起来也不方便，题目所以今天晚上就先发了dij部分，由上到下由易变难。 1.POJ 2387 Til the Cows Come Home（优先队列优化+邻接表） 2.poj 150...

2020-05-28

0 492

图论刷水题记录（二）（最短路-----SPFA算法）来自专栏

继第一篇的后续，又来刷水题了，写的是SPFA算法，这个算法的复杂度比较玄学，感觉能不用就不用了，但是他的好处就是可以判断负圈。 3月26日： 1.POJ 1847 Tram 题意：在一个交通网络上有N个路口, 每个路口指向多个方向, 默认驶向第一个方向, 驶向其他方向时需要进行一次操作, 求从a到...

2020-05-28

0 662

数据结构[栈与队列]的基本操作来自专栏

首先大致说一下栈这个数据结构，他是一个先进后出的结构，就好比家中摆盘子一样，洗好的盘子放到最上面，当要用的时候从最上面拿走（当然只是一般情况，你要是每次都从下面抽走盘子我也没办法）。这样的话我们可以直接用前面学过的线性表来实现，但是链的哪边是top呢？仔细分析一下就会发现如果我们用链的结尾作为to...

2020-05-28

0 635

[kuangbin带你飞]专题五查并集来自专栏

写了几个查并集得题，成功把自己写晕了之后写下面得题（写不下去了） **poj-2912 poj 文章目录 1.POJ - 1611（模板题） 2.HDU - 1213（模板题） 3.poj2236（稍稍复杂的查并集） 4.HDU - 1272（查并集判断图是否...

2020-05-28

0 743

[kuangbin带你飞]专题六-生成最小树来自专栏

先简单说一下，生成最小树一般常用两种算法，一种是prim另一种是kruskal，两种算法也各有利弊，比如说prim编程比较复杂一些而kruskal编程则相对容易一些，但是时间复杂度却差了些。 prim跟dijkstra差不多，简单来说prim适合稠密图，而kurskal则适合稀疏图。文章目录...

2020-05-28

0 453

图论-最短路Dijkstra算法详解超详有图解来自专栏

整体来看dij就是从起点开始扩散致整个图的过程，为什么说他稳定呢，是因为他每次迭代，都能得到至少一个结点的最短路。（不像SPFA，玄学复杂度）但是他的缺点就是不能处理带负权值的边，和代码量稍稍复杂。 dij算法（采用方法邻接表+优先队列优化）复杂度O(mn)降为O(mlogn) 不多哔哔，我们直...

2020-05-28

0 709