例题：受欢迎的牛
（Popular Cows）
学习tarjan，首先明确一些概念
强连通图是：在有向图中，任意两点都能直接或间接连通的图叫做强连通图
强连通分量：在一个有向图中，极大的强连通子图就是强连通分量
tarjan要用到两个数组low[]，dfn[]：
刚开始每个点的low值都等于dfn值 ，low是一个标记数组，
用来记录该点和该点的子树所能搜到的最早入栈的点的dfn值，也是找有没有后向边（后向边就是儿子指向父亲或祖先的边）
dfn值就是记录搜到该点的时间，也就是时间戳
如果low值与dfn值相等了，那么该点到栈顶元素之间（包含两者）的所有点属于一个强连通分量。
tarjan的一个用途就是来求强连通分量。
通过题目再来了解下这个算法
受欢迎的牛代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 500000;
int low[MAXN],dfn[MAXN],nxt[MAXN],to[MAXN],tot = 1,head[MAXN],scc[MAXN],sz[MAXN];
int n,m,xbt[MAXN];
struct Edge
{
int f,t;
}e[MAXN << 1];
void build(int ff,int tt)
{
to[++tot] = tt;
nxt[tot] = head[ff];
head[ff] = tot;
}
stack <int> s;
int tim = 0,scccnt = 0;
void dfs(int u)
{
low[u] = dfn[u] = ++tim;
s.push(u);
int v ;
for(int i = head[u] ; i ; i = nxt[i])
{
v = to[i];
if(!dfn[v])//如果下一个点没有在栈中
{
dfs(v);//搜到下一个点
low[u] = min(low[v],low[u]);//那我们的low值就是该点的low值和下一个点的low值中小的那一个
}
else if(!scc[v])//如果本来就在栈中了，并且没有涂黑（就是不属于其他强连通分量）
{
low[u] = min(low[u],dfn[v]);//low值的更新是取当前点的low值与搜到的点的dfn值中小的那一个
}
}
if(low[u] == dfn[u])
{
int x ;
scccnt ++;//数量++
while(!s.empty())//出栈操作
{
x = s.top();
s.pop();
scc[x] = scccnt;//这些点都属于一个强连通分量
sz[scccnt]++;//记录这个强连通分量的个数
if(u == x)
break;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i ++)
{
scanf("%d%d",&e[i].f,&e[i].t);
build(e[i].f,e[i].t);
}
for(int i = 1; i <= n; i ++)
if(!dfn[i])//刚开始所有点都是白点，也就是0，在搜的过程中变灰点，出栈后涂黑
dfs(i);//从没有搜过的开始搜
int ans = 0,q=0;
for(int i = 1; i <= m; i ++)
{
if(scc[e[i].f] != scc[e[i].t])//如果这个点与它所连向的点不在一个强连通分量
xbt[scc[e[i].f]] ++;//说明这个点所在的强连通分量不符合条件
}
for(int i =1; i <= scccnt; i ++)//scccnt是强连通分量的个数
{
if(!xbt[i])//如果符合条件
{
ans = sz[i];//sz[i]为第i个强连通分量所包含的点的个数
q++;//标记一下 （刚做的时候写的 q = 1结果bzoj居然能过，数据水~ ，但是poj就WA了，没考虑清楚的后果）
}
}
if(q == 1)//如果存在受欢迎的牛，有且只有一个强连通分量满足条件
{
printf("%d",ans);//输出个数
}
else
printf("0");
return 0;
}加了很多注释，但是关键问题还没讲，就是关于low值的更新问题，low值为什么要那么更新呢？让我们来看看tarjan的正确性（不严谨），如果我们找到一条后向边是指向第一个点或者他的祖先，那么这些点就都可以连通了，也就是构成了强连通分量，所以我们在找到可以搜的还没入栈的点时，low更新成小的那个，因为越往下搜，才越有可能找到那个最早入栈的点，而最早入栈的点的dfn值肯定是小的，那么如果是搜到的点已经在栈内了，也就是之前已经搜到了它，且low值没更新过，那我们的low值肯定是要更新成
搜到的dfn值，如果更新过了，也就是说可能low值变小了，如果low值小到比搜到的dfn值还要小，这意味着什么呢，就是说能找到更早的祖先，那就low值不变。这种思路是我把整体的分解成一个个小问题来想的（其实就是啰嗦），合起来不过短短两句代码
low[i] = min(low[i],dfn[j]) low[i] = min(low[i],low[j])
(j是在i前面入栈的点）等到low值与dfn值相等的时候，也就是形成了一个强连通分量，思想和上面那一堆话一样，紧扣这两个数组的定义，最好再去百度百科看看它的具体演示，我真的是懒得放图了，感觉百度百科的算法里对tarjan的讲解还是很良心的，以上都是看了几位大神的博客和百度百科后根据自己的理解的写的，如果有什么不对的地方，欢迎指出。