P2341 [HAOI2006]受欢迎的牛| 强连通分量 Tarjan 缩点

题目传输：https://www.luogu.com.cn/problem/P2341

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果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

第一次接触强连通分量和Tarjan 缩点

根据洛谷里大佬的优秀题解，如果存在明星奶牛（所有点都可以到达它），首先暴力跑所有点最短路会·T，那么先经过缩点后，当有且仅有一个点的出度为0；存在明星奶牛。当有两个及以上出度为0时，这两点互相不可达，就不能成为明星牛。

所以，过程是先进行缩点（将可以形成强连通分量（任意两点互相可达）的多点缩成一个点）；

然后计算出度为0点的个数；如果就一个那么输出该缩点中包含实际点的个数（缩点中，相互可达）；

有多个就不存在明星奶牛；

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=10050;
 4 typedef long long ll;
 5 struct ss
 6 {
 7     int u,to,next;
 8 } edge[N*20];
 9 int sumedg,head[N*20];
10 void addedg(int u,int v)
11 {
12     edge[sumedg]=(ss)
13     {
14         u,v,head[u]
15     };
16     head[u]=sumedg++;
17 }
18 int n,m;
19 int dfn[N],low[N];
20 stack<int>s;
21 int du[N],all[N],id[N];
22 //all[] 记录每个缩点中包含的点
23 // du[] 记录缩点的出度数；
24 int tot,gg;
25 bool insta[N];
26 void tarjan(int x)
27 {
28 
29     dfn[x]=low[x]=++tot;
30     s.push(x);
31     insta[x]=true;
32     for(int i=head[x]; i; i=edge[i].next)
33     {
34         int u=edge[i].to;
35         if(!dfn[u])
36         {
37             tarjan(u);
38             low[x]=min(low[x],low[u]);
39         }
40         else if(insta[u])
41             low[x]=min(low[x],dfn[u]);
42     }
43     int k;
44     if(low[x]==dfn[x])
45     {
46         ++gg;
47         do
48         {
49             k=s.top();
50             s.pop();
51             insta[k]=false;
52             id[k]=gg;
53             all[gg]++;
54         }
55         while(x!=k);
56     }
57 }
58 int main()
59 {
60     scanf("%d%d",&n,&m);
61     int u,v;
62 
63     for(int i=0; i<m; i++)
64     {
65         scanf("%d%d",&u,&v);
66         addedg(u,v);
67     }
68     for(int i=1; i<=n; i++)
69     {
70         if(!dfn[i])
71             tarjan(i);
72     }
73     for(int i=1; i<=n; i++)
74     {
75         for(int j=head[i];j; j=edge[j].next)
76         {
77             if(id[edge[j].to]!=id[i]) //记录每个点出度
78                 du[id[i]]++;  //id[]用于记录缩点后，一群点指向的点
79             //记录缩点的出度
80         }
81     }
82     int cnt=0;
83     for(int i=1; i<=gg; i++)
84     {
85         if(!du[i])
86         {
87             if(cnt)
88             {
89                 printf("0
");
90                 return 0;
91             }
92             cnt=i;
93         }
94     }
95     printf("%daa
",all[cnt]);
96     return 0;
97 }