Tarjan算法（求强连通分量/缩点）
题目：受欢迎的牛
什么是强连通分量？？？
1,强连通：在一个有向图中，如果两个点可以互相到达，就称为这两个点强连通。
2,强连通图：在一个有向图中，如果任意两个点强连通，就把这个图称为强连通图。
3,强连通分量：在一个非强连通图中的最大强连通子图，称为强连通分量。
至此，关于强连通分量的基本知识已经介绍完了，那么，Tarjan算法到底是什么东东？？？
Tarjan算法
tarjan算法是通过一次深度优先遍历来实现的，其中有几个重要的数组
1, dfn[]:表示结点i是第几个被搜索到的。
2，low[]:与结点i连接的所有点中dfn[]值最小的一个。
3,stack[]:栈里的元素。
4,flag[]:判断结点i是否在栈里。
因为连通分量里的任意两个点都是强连通的，当存在一个连通分量的时候，点u一定会与它的祖先连通。因为low值代表的是它儿子中dfn[]值最小的，所以它的low值就会更新，从而小于它的dfn[]的值。
当一个点的low[]值等于它的dfn[]的值的时候，说明u点的儿子们没有指向他们祖先的了，所以此时u点与它的子孙们构成了一个连通分量。
缩点
接下来缩点这个步骤就是这题的关键。
首先我们得知道什么是缩点，当我们找到一个连通分量的时候，因为这个连通分量里的点都是强连通的，所以我们可以把它们看成一个点。
当我们把每一个连通分量都进完缩点时，我们只需要在剩下的这张图中找明星就行了，如果这张图里的每一个点都是强连通，那么显然这张图里的牛都是明星。否则我们可以找到出度为0的牛，这样可以保证其他所有的牛都喜欢它，但是如果有2个以上的出度为0的牛，那么很显然这张图里是不存在明星的。
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int w[10003],c[10003];
struct node{ //链式前项型存图
int from;
int to;
int next;
}a[100003];
int head[190003],Dfn[100003],Low[100003],fl[100003],stack[100003],color[100003],cnt[100003],du[100003],t,tot,k;
//stack[]记录栈里的元素
//fl[]为记录当前节点是否在栈里
//color[]就是把所有的连通分量都变成一个颜色，也就是缩点
//cnt[]记录每个连通分量里的元素个数
//du[]就是在缩完点之后，记录每个点的出度为多少
void dfs(int i)
{
Dfn[i]=Low[i]=++tot; //表示点i是第几个被遍历到的，把low[i]的值先赋值为dfn[i]的值
stack[++k]=i; //点i入栈
fl[i]=1; //入栈所以点i变为1
for(int j=head[i]; j; j=a[j].next) //遍历与这个点相连的所有点
{
if(!Dfn[a[j].to]) dfs(a[j].to),Low[i]=min(Low[i],Low[a[j].to]); //如果与它相连的这个点没有被遍历过，就往下遍历，并比较它和子孙的low[]值
else if(fl[a[j].to]) Low[i]=min(Low[i],Dfn[a[j].to]); //否则如果这个点在栈中，表示他们都在一个连通分量里
}
if(Low[i]==Dfn[i])
{
t++; //每个连通分量的标号
do{
color[stack[k]]=t; cnt[t]++; //cnt记录每个强连通分量里有多少个数
fl[stack[k]]=0; //出栈
k--;
}while(i!=stack[k+1]);
}
}
int main(){
int n,m,x,y;
cin>>n>>m;
for(int i=1; i<=m; ++i)
{
cin>>a[i].from>>a[i].to;
a[i].next=head[a[i].from];
head[a[i].from]=i;
}
for(int i=1; i<=n; ++i)
if(!Dfn[i]) dfs(i);
for(int i=1; i<=n; ++i)
{
for(int j=head[i]; j; j=a[j].next)
{
if(color[i]!=color[a[j].to]) //缩完点之后判断每种颜色的出度为多少
{
du[color[i]]++;
}
}
}
int ans=0;
for(int i=1; i<=t; ++i)
{
if(du[i]==0) //找到度为0的点
{
if(ans) {cout<<0; return 0;
}
ans=i;
}
}
cout<<cnt[ans];
return 0;
}