一、强连通图 在有向图中，任意两个顶点互相可达。
强连通分量 在有向图中，极大的强连通子图。
我们需要求出如下信息：
1)、有几个强连通分量，他们的编号分别是几？
2)、每个强连通分量分别有几个点？
3)、每个点属于哪个强连通分量？
二、Tarjan算法 是基于对图深度优先搜索(DFS)的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的结点加入一个栈，回溯时可以判断栈顶到栈中的结点是否为一个强连通分量。具体操作：
1、维护几个数组
dfn[i]：走到i点的时间戳（时间序）;
low[i]：i点能访问到的最小时间序
si[t]：编号为t的强连通分量中点的数量；
id[i]：编号为i的点所属强连通分量
stack：走过的没有被去除强连通分量的点；
bool inst[i]：标记i点是否在栈中
2、求解原理
1)、dfs走到x：dfn[x]=low[x]=++times;
2)、遍历x的出边，指向to
>>>A. to没有访问过，dfs访问to，访问to结束，后退，low[x]=min(low[x],low[to])
>>>B. to访问过，且在栈中，low[x]=min(low[x],dfn[to])
3)、从x点后退，要判断x是否是“入口”，如果是(即low[x]==dfn[x])，从栈顶开始弹出元素直到x，将这些元素统计到同一个强连通分量中。
时间复杂度 Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(n+m)。（n表示点数，m表示边数）
三、Tarjan与缩点
什么是缩点 缩点是一种图论算法，用于将有向图的强连通分量缩成一个结点，并构造一个新的有向无环图(DAG)。这个新的图中的每个结点代表原图的一个强连通分量。
所有能走到点x的那些点，在拓扑排序的结果中，一定是出现在点x之前的。因此拓扑排序的结果，是复合DP中的无后效性的。
f[i]：以点i结尾的经过数字和的最大值。
边界：如果din[i]==0，说明点i不受其他点的影响。
f[i]=w[i]。
状态转移方程：f[to]=max(f[to],f[h]+w[to]);
如果h点要出队了，用到h的最优解，更新h能走到的to的最优解。
最终答案：max(f[i])。
四、有向无环图（ DAG ）有许多重要的性质：
1．拓扑排序： DAG 可以进行拓扑排序，即按顺序列出所有顶点。这可以用于寻找依赖关系，或确定执行顺序。
2．单源最短路径： DAG 上可以使用拓扑排序和动态规划算法计算单源最短路径。
3．DAG上必然存在出度、入度为0的结点。
4．DAG上若存在唯一出度为0的结点，则该结点可被 DAG 上其他所有结点到达。
5．问在 DAG 上最少选择多少个点能够使得从这些点出发可以到达所有点，那么答案就是入度为0的点的个数。
6．假设 DAG 上出度为0的结点有 a 个，入度为0的结点有 b 个，那么再加 max(a,b)条边可以使得该有向图强连通。