标签:图论

有向图强联通分量 Popular Cows

有向图强联通分量 Popular Cows

在yy就看了这道题,可是当时抄板子都没过,距离第一次尝试理解tarjan也很久了,今天写了两道题,怕是能写出来了……
poj The Popular Cows

0
省选复习第一篇——图论

省选复习第一篇——图论

首先,我们已知一个图G={V,E},V代表了这个图的顶点的个数,E代表了图中的边。
那么不管我们要进行什么操作,我们面临的第一个问题是如何存图?

一、存图

1、邻接矩阵
建立一个二维数组a,a[i][j]表示i为起点,到j有一条边,权值为a[i][j]。< 初值赋值为-1或INF >
听起来挺简单,但是只能满足较小的数据范围

2、邻接表
据说:对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费
对于每个顶点i,我们可以从i指针向下,指到i能到达的以一个点k,k再直到i能到达的下一个点j,……
所以这样我们就会形成n个链表,然后从起点开始向后遍历,就是从i点出发到达的所有点了
如图:

3、链式前向星
这个就是重点了!
类比邻接表的思想,我们只要记录一个顶点及出度的边,我们就知道他能去到的点。但是对于每条边,我们都知道起点,也就是说,其实我只要知道边,就不需要记录我的起点和终点了。况且指针实现也不是很简单,所以我们就引入了一个新的存图方法。
在链式前向星中,我们会记录每条边的终点,上一条以这个起点为起点的边的序号,以及这条边的权值。
为什么不记录起点呢?
因为我们在类比邻接表的时候,想到了可以把边连接起来,所以我只要把从同一个起点出来的边连到一起,然后将最后一条边的序号记录到一个head数组中,就可以轻松访问以此为起点的所有边了啊!是不是很妙啊~
那么我们先看一下代码,再增强我们的理解:

因为我们add(u,v)时,是存进去了一条u到v的边,所以如果这是一个无向图,我们一定要反过来再add一遍。
head[i]指向i为起点的最后一条边cnt,然后通过edge[cnt].next继续访问i为起点的边,这样我们就可以很轻松的做到dfs和bfs了!

二、树
鉴于树是一种比较简单的图,所以我们先来看树的图论。

1、树的直径
对于一棵树来说,我们有根节点和很多叶,那么就存在两个节点,使得这两点间的距离在这颗树中是最长的,我们就称以这两点为端点的“线段”为树的直径。
那我们怎么求树的直径呢?
首先,要想求这样一条线段,我们一定要知道它的一个端点,然后就可以通过bfs求出另一个端点,然后树的直径就诞生了!
那么我们怎么求这个端点呢?
我们可以通过dfs(或者bfs)来找到从树上任意一点i能到的最远点,但是我们怎么知道这个搜到的点一定在树的直径上呢?
① 如果这个点在树的直径上(但不是端点),那么这是不可能的,因为我一定会继续向前搜索来到直径的端点上。
② 如果这个点不在树的直径上,假设我们从这个点再一次bfs出来的路径(UV)与直径(ST)相交,那么我们可以反正一下:

如果我得出uv为直径那么iv是大于it的,这与ST是直径不符,所以不成立!
//假设我们得到的这个路径与直径不相交,事实上这是不成立的……

所以我们得到答案代码!

2、最近公共祖先
LCA倍增: 不会!
st表:我懒了,那么点击吧

3、最小生成树
介于有些人写的比较早,那么点击把~

三、图
讲真,对于图来说,我们能做的操作有很多~

1、求最短路
(1) 单源最短路spfa
当我们想知道一个点到图中其他任意一点的距离时,我们可以利用宽搜的思想,然后结合dp的maxmin,我们就可以来看一下这个spfa代码

vis记录我当前点i是否在队列中,dis[i]代表x到i的距离,我们每搜到点j便查看我从当前“原点”到对首r加上r到i的距离是否小于当前“原点”到i的距离,若小,则更新它。
是不是特别容易理解??那我们来看另一种代码极其简单的多源最短路。

(2) 多源最短路 floyd
我们如果会随机访问一点i到一点j的距离,那么我们还是预处理出来比较妙~
那么我们的dp思想一定要发挥的淋漓尽致~!(显然,我也不是很清楚三维的转换)

!!注意,顺序一定要为kij!!

1+