简单的定义强连通：
一个环，或者多个环相套，
则一个强连通中的任何点都可以互相到达
随手一个简单强连通，
1->2->3->1
思考程序如何才能让计算机模拟人的眼睛，判断出这是一个强连通，
肯定要按照边的连通情况，遍历图，
这里显然dfs比bfs更合适，所以我们按照1->2->3的顺序遍历
接下来到了3->1的边，这个边肯定有特征，让计算机确定这是一个强连通
我们发现：
1）1号点已经遍历过
2）这是一条回边
这样我们可以设一个dfn的量，保存每个点遍历时的时间前后
现在我们看我们找强连通是为了什么：
1）计算有几个强连通
2）把环去掉，叫做tarjan缩点
那么对于目的1）
我们的计数肯定是记每个强连通的结束的点，
就是最先遍历的那个点，
那这个点的特征（和别的点的区别）在哪呢？
答案是他没有回边，就是他的子节点遍历中，遇不到一个点的dfn比他早
那么我们可以找一个记录的量，先叫做t，
这个t应该是记录每个点子节点中dfn的最小值
（因为最高点的dfn最小，其他的都比他的dfn大，那么我们要记录的就是dfn的下限）
那么我们就把t改成low，好听，不易重名
思路就出来了，找没有遍历过的点遍历，
在3节点时，找能到达的点集合，如果有一个遍历过的点，那他的dfn一定小，
我们就更新3节点
为了让2,这种中间点的dfn也发生改变，那么在2->3之后，也要更新2的dfn
所以我们的结构就出来了
但是那些遍历过的点，可能是别的强连通分量中的，所以一个stack，每次找完弹出一个强连通
ps：
1）tarjan中单个点也算一个强连通
2）这里找到的是最大强连通分量，小的没管
for(int i=1;i<=n;i++)//时间戳1：代表访问过没有 if(!dfn[i]) tarjan(i); bool f[N]; stack <int> s; int dfn[N],low[N],ans; void tarjan(int x) { printf("%d %d ",x,tt+1); dfn[x]=low[x]=++tt; s.push(x);f[x]=true; for(int i=head[x];i;i=e[i].nx ) { int v=e[i].v ; if(!dfn[v]) { tarjan(v); printf("1:%d ",v); if(low[x]>low[v]) printf("a "); low[x]=min(low[x],low[v]); } else if(f[v]) { printf("2:%d ",v); if(low[v]>=low[x]) printf("b "); low[x]=min(low[x],low[v]);//这里用时间戳进行比较，因为时间戳大小表示先后 } } if(low[x]==dfn[x]) { while(s.top() !=x) f[s.top() ]=false,s.pop() ; f[x]=false,s.pop() ; ans++; } }
对于目的2）
看题！
poj2186 Popular Cows
告诉你有n头牛，m个崇拜关系，并且崇拜具有传递性，如果a崇拜b，b崇拜c，则a崇拜c，求最后有几头牛被所有牛崇拜。
缩点思路：将一个强连通分量->变成超级源点
这个超级源点，用fa表示，或者用新的sum=n,++sum也行
主要区别：
if(dfn[u]==low[u]) { color[u]=++sum; vis[u]=0; while(stack[top]!=u) { color[stack[top]]=sum; vis[stack[top--]]=0; } top--; }
注意，缩点之后的边要区分强连通内，和强连通外，
入度出度统计都要重新注意