知识一览：
- 最短路：
- Dijkstra（堆优化）
- SPFA
- Floyd
- 最小生成树：
- Kruscal
- 连通性：
- BFS
- Tarjan（强连通分量）
- 其它：
- 拓扑排序
- LCA
先先先先看个题：
【题目描述】
现有一个传动系统，包含了N个组合齿轮和M个链条。每一个链条连接了两个组合齿轮u和v，并提供了一个传动比x: y。即如果只考虑这两个组合齿轮，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。传动比为正表示若编号为u的齿轮顺时针转动，则编号为v的齿轮也顺时针转动。传动比为负表示若编号为u的齿轮顺时针转动，则编号为v的齿轮会逆时针转动。若不同链条的传动比不相容，则有些齿轮无法转动。我们希望知道，系统中的这Ｎ个组合齿轮能否同时转动。
N<=1000，M<=10000；
朴素30pts：
把每两个点间的所有路径都搜索一遍，比例相乘，比较是否相同；
正解：
考虑图的性质：
图的dfs树的非树边只有返祖边没有横叉边；（自己画一画可以理解）
从任意一点开始dfs，求出dfs树；在dfs树上，传动比唯一确定，我们按照传动比设定权值为c1，c2……
枚举非树边，若非树边上的比例与所指两点求得权值比例不同，就不可以同时转动，否则可以；
看知识：
LCA：
重课表也是神奇；
O(nlogn)
是一种在线算法，可以边询问边求解；
然后Tarjan（对，没错，又是这个人）提出了一种线性的求LCA的方法O(n+m)，但是是离线的；
最短路：
单源最短路：
堆优化的Dijstar：
要求：边权全是正权；
pa =>pair<int,int> <源点到此点当前最短路，此点编号>，然后是首先按第一维比较的
求1=>所有点最短路；
先把最短路都赋成正无穷；
不断从队顶弹出元素，直到队空；
如果处理过，不再处理；
Else 处理：
枚举从now出去的每一条边，如果到now的最短路+某条边的路<某条边终点的最短路，修改终点最短路；
SPFA：
可以处理带负权的图，判负环；（最长路代码：：：：：）显然可以直接stl
多源最短路：
Floyd 要深刻理解DP的原理？（也没讲啊？？？）
翻找之前的博客：
- floyd实际上是一个DP（floyd：哈哈想不到吧qwq）
- floyd其实是一个三维DP
- floyd其实就跟01背包一样把k这一维降掉了，因此k要放在最外层枚举；
- 对于没有降维的三维floyd disk,i,j来讲，表示的是从i=>j只可能经过1——k这些点的最短路径；
最小生成树：
最小生成树上的最大边权一定最小；
Kruscal：
处理无向图的最小生成树
思想：先把所有边拿出来排个序，每次选取边权最小的一条边，将其连入同一个连通块中（要注意不能出现环）
有向图最小生成树：朱刘算法
拓扑排序：
应用条件：有向图
每次将入度为0的点拿出来，排一个序。
考法1：在拓扑序上进行动态规划；（大概zhx会将伐？）
考法2：判环；
强连通分量&tarjan：
定义在有向图当中；
两个点是强连通的：在图中有一条路径可以由点A=>B,还有一条路径可以由B=>A；
每个点都强联通，强连通图；
一个图的一个子图是强连通图，被称为强连通子图；
一个图中极大（最大）的强连通子图，称为强连通分量；
以受欢迎的牛举例，讲Tarjan：
很容易可以想到，每个强连通分量中的牛都互相喜欢；
把所有的强连通分量缩成一个点，看有几个点没有出边；如果有大于1个点没有出边，那么没有答案，如果恰好有1个点没有出边，那么这个点代表的强连通分量大小就是问题的答案；
如何求强连通分量：
1.dfs尝试操作；
2.Tarjan：
首先要建立一棵dfs树：
原图：
dfn(x)表示x是第几个被dfs到的
Low：当前节点以及它的子树的所有出边，能够连到的dfn值中最小的一个
建图：
蓝色边表示非树边
Dfs，加到一个栈里，当dfn==low时，说明是一个强连通分量，一直弹出直到弹出到我们刚刚算出的dfn==low的数x，然后这些被弹出的数都是一个强连通分量；
上面图中，第五个节点的low按照定义应该为4，但是因为之前扫描到6时，我们把6删掉了，因此low[5]=5;
上代码：
