2020/10/25笔记，概念
连通图
- 无向图\(G\)图上任意点 \(i\)到\(j\)都有路径对其联通，则就称这叫连通图
- 在有向图中，\(i\ -\ j\) 必须同向的，如果有 \(\ i - j\ \& \ j\ -i\),则该有向图叫做强连通图
连通分量
- 无向图 \(G\) 中，极大连联通子图叫联通分量
- 任何联通图的连通分量，即本身
- 非联通的无向图有多个连通分量
个人觉得问题主要在于这个极大的理解。这个极大是指的边数（edge）极大，这个极大是在原图的边中的极大（也就是说，子图里面已经包括了原图中所有和子图中顶点有关的边）。
之所以用极大而不用最大，是因为不仅仅有一个连通分量，这个和数学中的极大值以及最大值的区别是一样的。
极大
当前 强联通 子图与原图中有关点的边数之和最大。
联通 无向图 有多个 联通子图 ，每个子图都是一个联通分量，
强连通分量
- 极大强联通子图即该有向图的强连通分量。（非强联通有向图）
Tarjan(非本人)
算法思路：
-
首先这个图不一定是一个连通图，所以跑Tarjan时要枚举每个点，若dfn[ ] == 0，进行深搜。
-
然后对于搜到的点寻找与其有边相连的点，判断这些点是否已经被搜索过，若没有，则进行搜索。若该点已经入栈，说明形成了环，则更新low.
-
在不断深搜的过程中如果没有路可走了（出边遍历完了），那么就进行回溯，回溯时不断比较low[ ]，去最小的low值。
-
如果dfn[x]==low[x]则x可以看作是某一强连通分量子树的根，
-
也说明找到了一个强连通分量，然后对栈进行弹出操作，直到x被弹出。（自己写不出阿里，就粘贴一下）
Tarjan （个人理解）
给一组数据：
表示 \(u\rightarrow v\) 的有向边
1 2
1 3
2 1
3 1
显然这是一个非联通图（因为3不能到2），则存在两个强连通分量
给一组数据
表示 \(i\) 的low[]
1 1
2 1
3 1
但是构成的可不是 \(1\rightarrow 2\ \rightarrow 3\ \rightarrow1\) 的大环。
运输计划
无向联通图，不存在环
删边后是最长距离最短，二分查找
思考 \(m\) 个运输计划，\(u - v\) 的路径会不会有多条？
答案是：不会！
-
也就是说 \(u - v\) 只有一条路径
-
dis[v]表示v点到祖先节点的距离
-
f1,f2,是将各个点以并查集的方式形成树，当查询两点间的链长时，找到他们的fa,即LCA（很神，神在他们完全遍历完整个图，只需要遍历完自己需要到达点的内容即可进行链的操作）
-
链长\(=\) dis[u]+dis[v]-2*dis[lca]
树上差分
剩下的就是树上差分了
我的目的是 Tarjan
发音
Tarjan（te,jian ）~（纠正发音）
\(To \ be \ continue...\)