树上跑一边DFS的代码很简单吧，图上的DFS与其相差无几。区别在于图上的DFS要记录每一个点是否被遍历过，如果已经被遍历过了，则跳过该点继续DFS；此外这个图有可能是个不完全连通，所以要确保每个点都被遍历到。
由此我们就知道一些有用的东西了，比如图中各点的DFS序，或者按照DFS序建一棵树：DFS生成树。
如上图，这就是一个在有向图中的一棵DFS生成树的例子。可以看见，在图中除了黑色的构成树的实边以外，还有一些虚边，它们不存在与生成树中，但却在原图中存在。对于这些边，我们可以给它们分别命名：
如果一个有向图中每一个点都能相互到达，则称该图为强连通图。一个图的极大子图如果是强连通图，则这个子图为该图的一个强连通分量。
在有向图中求强连通分量最经典的算法就是Tarjan算法了。Tarjan算法的基本思路就是在DFS整个图的同时为每个节点保存两个信息：
其实就是DFS序。
从该节点的子树出发，经过一条B边或C边可以到达的DFS序最小的在栈中的DFS序。
用这两个信息，就可以在DFS的同时找环了，而根据强连通分量的定义易知：一个环一定是一个连通分量。
所以为了方便维护这两个信息，我们引入一个栈，对于遍历到的一个点u，栈中保存已遍历过的，能通过某条路径到达u的节点。以此来将一个强连通分量里的可能点囊括到一起。
并且我们还需要一个bool数组来记录一个点是否在栈中。
Tarjan算法的关键就在于low，所以在DFS的过程中我们主要针对对low数组的更新来进行说明。当DFS遍历到一个点u时，对于其接下来将要遍历的节点v与二者之间的边e，分三种情况考虑：
语言无力，多说无用，不如直接上伪代码：
另外，如果一个点的所有子树都遍历完了，判断一下其DFS序与low的值的大小，如果发现其DFS序与low值相等，说明这个点是一个强连通分量的“根”，于是不断弹栈，直到将这个点也弹出来，这之前弹出的所有点都与其在同一个强连通分量中。
对于其正确性，不妨这样想：对于每一个强连通分量，有且仅有一个节点的DFS序与low值相等，且该节点一定是在DFS过程中第一个被遍历到的。因此其DFS序最小，所以更新low时不会被其下方的节点所影响。
而栈中在其之上的所有节点就是它能到达的所有节点，这也就说明其能到达的所有节点无法再到达在其之上的任何一个节点，这在代码中表现为low值比其大，不可能比其小，因为这样会在DFS过程中使其更新low值。以上，证毕。
那么说了这么多，强连通有什么用呢？想一想，一个强连通分量中的所有点都可以相互到达，那么不计较经过边数的话，如果一个节点可以到达强连通的其中一个点，那么必然也可以到达强连通的其它点。所以我们可以将一整个强连通分量坍缩成一个点，由此对图中每个强连通分量都进行缩点操作，就可以将一个有向图变成DAG（有向无环图）来解决问题了。这就是缩点。
如果原图是连通图，那么缩点之后就会变成一棵树。
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜欢B，B喜欢C，那么A也喜欢C。牛栏里共有N头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。
强连通版子题。不妨这么想：每头奶牛视作一个点，爱慕关系为有向边，则我们可以建一个图。而图中每个强连通分量中的每个点都可以相互到达，即相互爱慕，那么我们就可以将其视作一个点。
对每一个强连通分量，记录其中总点数。缩点完成后再遍历一次新的树，找到叶子节点。因为非叶子节点的子节点无法再到达它，即无法被子节点“爱慕”，只有叶子节点可能被所有点到达。
但还需要再考虑一件事，如果有多个叶子节点，那么这些叶子节点一定不可能互相到达，所以一定没有符合条件的奶牛。只有在只有一个叶子节点时，才输出该叶子节点中包含的点数。
以下为代码：
一个有向连通图中，燃烧每个点都需要一定费用。如果从某点出发能从一条路径回到该点，那么燃烧这条路径上所有点的总费用就等于这个点所需的费用。现在想燃烧所有的点，每个点可以重复经过。
虽然题面让人看得感同身受，但题目还是很简单的。首先求出强连通分量，然后记录下每个强连通分量中的最小值的点的点数，根据乘法原理，将这些数量相乘就是总方案数。别忘了边乘边模。
这题将缩点和最短路结合了，需要在scc上跑最短路。
这两题就当作思考题吧，都是强连通必刷题。
除Tarjan算法以外，还有几种求强连通分量的算法，如Kosaraju算法、Garbow算法等。想了解的可以去OIwiki自行查看。