那么我们一个简单的代码就可以写出来了：
void tarjan(int u){ dfn[u]=low[u]=++cnt; s.push(u); ins[u]=1; for(int i=0;i<gpe[u].size();i++){ int v=gpe[u][i].to; if(!dfn[v]){//如果节点未访问，则访问之 tarjan(v); low[u]=min(low[u],low[v]); }else if(ins[v]){//ins是为栈中节点做的一个标记 low[u]=min(low[u],dfn[v]); } } }当更新完毕之后，我们需要找出一个完整的scc，因为我们提前已经用辅助栈来记录节点了，剩下的工作就只剩下从栈中不停地pop就完事了
if(low[u]==dfn[u]){ ins[u]=0; scc[u]=++sccn;//sccn是强连通分量的编号 size[sccn]=1;//size记录了强连通分量的大小 //找到某一个low[u]==dfn[u]的节点的时候就要立即处理，因为这个节点也属于一个新的scc while(s.top()!=u){ scc[s.top()]=sccn;//scc[u]记录了u点属于哪一个scc ins[s.top()]=0; size[sccn]+=1; s.pop(); } s.pop(); //这里pop掉的就是一开始的那个low[u]==dfn[u]的节点。因为相关信息已经维护完毕，所以这里直接pop也没问题 }把这两部分结合在一起，就是tarjan求scc的完整代码了：
void tarjan(int u){ dfn[u]=low[u]=++cnt; s.push(u); ins[u]=1; for(int i=0;i<gpe[u].size();i++){ int v=gpe[u][i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(ins[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ ins[u]=0; scc[u]=++sccn; size[sccn]=1; printf("%d ",u); while(s.top()!=u){ scc[s.top()]=sccn; printf("%d ",s.top()); ins[s.top()]=0; size[sccn]+=1; s.pop(); } s.pop(); printf("\n"); } return; } tarjan与缩点tarjan算法最有用的地方就是缩点了。缩点，顾名思义，就是把图上的某一块的信息整合成一个点，从而使得后续处理的速度加快（个人的简单总结，可能会有遗漏之类的）。
先来一个模板题吧：
P2341 受欢迎的牛 G
emmm......题目大意就是对于一条边u->v代表了u喜欢v ，然后给出了一个奶牛和奶牛之间的关系网(不要问我为什么是奶牛，这不是usaco题目的传统艺能吗)，要你求出这群奶牛之中的明星奶牛。明星奶牛就是那些被所有奶牛所喜欢的奶牛。这里要注意，喜欢是可以传递的，也就是说a->b，b->c，那么a->c。(更多题目细节可以去连接里面看看)
首先最朴素的dfs方法就是对于每一个点来检查喜欢它的节点的数量，但是这样的效率肯定是太低了，所以我们考虑缩点。如果在这个关系网内部存在某一个强连通分量，也就是说这个分量里面的每一个奶牛都是互相喜欢着的，并且任何喜欢这个分量的奶牛都会喜欢到这个分量内部的每一个奶牛，于是我们可以把这个分量当成一个点来看待。
缩点结束之后的新图肯定是一个DAG(有向无环图)，又因为缩点本身对题目是没有影响的，所以我们可以基于这个DAG来分析题目，比之前算是简单许多了。
很明显，一个DAG里面只能有一个明星牛(或者是由明星牛组成的SCC)，因为当存在两个的时候他们是无法互相喜欢的(如果互相喜欢的话就会被缩成一个点)
答案就很明显了，我们只需要维护每一个SCC的出度(出度为0则证明这就是一个明星)，如果存在两个或两个以上的明星则证明这个图里面没有明星。如果只有一个的话我们就在tarjan里面顺手维护每一个scc的大小，最后统计一下输出就完事了
AC代码:
#include <bits/stdc++.h> using namespace std; const int maxn=10010; struct edge{ int to; edge(int to_){ to=to_; } }; vector<edge> gpe[maxn]; int dfn[maxn],low[maxn],ins[maxn],scc[maxn],size[maxn],cnt=0,sccn=0; stack<int> s; void tarjan(int u){ dfn[u]=low[u]=++cnt; s.push(u); ins[u]=1; for(int i=0;i<gpe[u].size();i++){ int v=gpe[u][i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(ins[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ ins[u]=0; scc[u]=++sccn; size[sccn]=1; while(s.top()!=u){ scc[s.top()]=sccn; ins[s.top()]=0; size[sccn]+=1; s.pop(); } s.pop(); } return; } int n,m,oud[maxn]; int main(void){ scanf("%d %d",&n,&m); memset(low,0x3f,sizeof(low)); memset(ins,0,sizeof(ins)); for(int i=1;i<=m;i++){ int u,v; scanf("%d %d",&u,&v); gpe[u].push_back(edge(v)); } for(int i=1;i<=n;i++){ if(!dfn[i]){ cnt=0; tarjan(i); } } for(int u=1;u<=n;u++){ for(int i=0;i<gpe[u].size();i++){ int v=gpe[u][i].to; if(scc[u]!=scc[v]) oud[scc[u]]++; } } int cont=0,ans=0; for(int i=1;i<=sccn;i++){ if(oud[i]==0){ cont++; ans+=size[i]; } } if(cont==1){ printf("%d",ans); }else{ printf("0"); } return 0; }代码以前写的，略冗长，见谅
题目推荐：
真·模板题： P2863 [USACO06JAN]The Cow Prom S
P1262 间谍网络
P2746 [USACO5.3]校园网Network of Schools