上一次我们详细介绍了强连通分量的Tarjan算法，今天呢，我们来做一些习题来巩固Tarjan算法，毕竟它十分重要。
上面是上一次的详解，在做题时可供参考。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
练习一般采用洛谷题库。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
T1. luogu P2341 受欢迎的牛 来源： HAOI2006
题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶
牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜
欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你
算出有多少头奶牛可以当明星。
输入输出格式
输入格式：
第一行：两个用空格分开的整数：N和M
第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B
输出格式：
第一行：单独一个整数，表示明星奶牛的数量
输入输出样例
说明
只有 3 号奶牛可以做明星
【数据范围】
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000
分析
对于奶牛之间的关系，不难看出，可以用一个有向图表示。奶牛A喜欢奶牛B，则转化为节点A到节点B有一条有向边。
然后，我们再来分析一下样例，并从中找到解题方法，解题思路。
这，是我们将奶牛之间的关系转化而来的有向图。
不难发现，节点1与节点2形成了强连通分量。我们一看到强连通分量，就要先想到缩点，把问题简单化，不行再想别的方法。
这是缩点之后的样子。变成了一个非常简单的图。
那么，接下来怎么办呢？
样例是说只有3号奶牛是“明星”，我们就来看3号奶牛有什么特点。
当我们缩完点之后，这个有向无环图（DAG）中，不会再有强连通的两点，于是可以得出两点之间最多只有一条有向路径，也就是不存在两只牛互相喜欢。（我们把构成强连通分量的点看做是一只牛）。
这说明什么呢？
这说明若一直奶牛是明星，那在缩点之后，它一定不会喜欢任意一头奶牛。这在有向图中叫出度为0。也就是说它没有去别的节点的路径。
如果缩点之后一个由强连通分量组成的节点时明星，则属于这个强连通分量的所有节点都是明星。（他们互相喜欢）。
这样一看，题目就变得简单了。
解题过程也很明了：
1.通过奶牛的关系建立一个有向图。
2.使用Tarjan算法把强连通分量缩成一个点。
3.遍历缩点后的有向图，找出出度为0的节点，加到Ans中去。
4.得解。
分析了这么多，大概可以AK了吧。
这题思路没有问题，但在一些细节上需要注意，不要掉坑。
接下来开始填坑。
1.100%的数据N<=10000,M<=50000
数据范围：10000点，于是int的二维数组开不下10000^2，所以存图时建议使用vector（不定长数组）或 链式前向星 来存图。
vector存图：大佬的博客
链式前向星存图：大佬的博客
以上两个博客介绍了这两种优秀的存图方法，不会的可以看一看。
2.有一个大佬说：我们只关注一个分量的出度是否为0，所以不用判断两个分量间的边是否重复统计
3.另一个大佬说：数据水
好吧，也就这些了，最后给代码：
code：
1 #include<bits/stdc++.h> 2 #define maxn 1000000 3 using namespace std; 4 int Next[maxn],a=0,F[maxn],Head[maxn],cmpi[maxn],out[maxn],E[maxn],cmp[maxn],s[maxn],dfn[maxn],low[maxn],top=0,cmpid=0,tim=0; 5 bool V[maxn],D[maxn]; 6 void ins(int x,int y,int i) 7 { 8 E[i]=y; 9 Next[i]=Head[x]; 10 Head[x]=i; 11 }//链式前向星写法，详见博客 12 int find() 13 { 14 int ans=0; 15 for(int i=1;i<=a;i++) 16 { 17 for(int p=Head[F[i]];p;p=Next[p])//列举这个点的所有邻接点 18 { 19 if(!D[E[p]])ans++;//如果这个点的邻接点不和他在一个强联通分量的话，那么我们就发现他所在的分量有了出度 20 } 21 } 22 return ans; 23 }//找一组强连通分量的出度，若为0，下面的答案就累加 24 void tarjan(int u) 25 { 26 dfn[u]=low[u]=++tim; 27 s[++top]=u; 28 V[u]=true; 29 for(int p=Head[u];p;p=Next[p]) 30 { 31 int y=E[p]; 32 if(!dfn[y]) 33 { 34 tarjan(y); 35 low[u]=min(low[y],low[u]); 36 } 37 else 38 { 39 if(V[y])low[u]=min(low[u],dfn[y]); 40 } 41 } 42 if(dfn[u]==low[u]) 43 { 44 int y; 45 cmpid++; 46 do 47 { 48 y=s[top--]; 49 V[y]=false; 50 F[++a]=y;//将这个点存入暂时数组 51 D[y]=true; 52 cmpi[cmpid]++; 53 }while(y!=u); 54 cmp[cmpid]=find();//cmp存储他的出度 55 a=0; 56 memset(D,false,sizeof(D));//D数组表示这个点在不在这个强连通分量 57 } 58 }//Tarjan算法缩点，模板在我的博客里有 59 int main() 60 { 61 int n,m; 62 scanf("%d%d",&n,&m); 63 for(int i=1;i<=m;i++) 64 { 65 int a,b; 66 scanf("%d%d",&a,&b); 67 ins(a,b,i);//建图 68 } 69 for(int i=1;i<=n;i++) 70 if(!dfn[i])tarjan(i); 71 int c=0,ans; 72 for(int i=1;i<=cmpid;i++) 73 if(!cmp[i])c++,ans=i;//检查图是否连通 74 if(c==1) 75 printf("%d",cmpi[ans]); 76 else 77 printf("0"); 78 return 0; 79 }
希望大家在不抄题解的情况下能写对代码，多理解，多总结，这对你们帮助很大。
好了，今天的讲解就到这里，之后还会有习题分享给大家，我们下次见。
