洛谷P2341 [HAOI2006]受欢迎的牛|【模板】强连通分量（Tarjan+缩点）

题目描述

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

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

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N=1e5+5;
 5 int top,tot,n,m,tag;///tag为强连通分量的编号
 6 int Stack[N];
 7 bool inStack[N];
 8 ///belong[i]表示编号为i的点属于哪一个强连通分量，du[i]表示编号为i的强连通分量的出度
 9 int dfn[N],low[N],belong[N],du[N];
10 vector<int> g[N];
11 
12 void tarjan(int u){
13     int v;
14     dfn[u]=low[u]=++tot;
15     inStack[u]=true;
16     Stack[++top]=u;
17     for(int i=0;i<g[u].size();i++){
18         v=g[u][i];
19         if(!dfn[v]){
20             tarjan(v);
21             low[u]=min(low[u],low[v]);
22         }
23         else if(inStack[v]){
24             low[u]=min(low[u],dfn[v]);
25         }
26     }
27     if(dfn[u]==low[u]){
28         tag++;
29         do{
30             v=Stack[top--];
31             inStack[v]=false;
32             belong[v]=tag;///属于同一个强连通分量
33         }while(u!=v);
34     }
35 }
36 
37 int main(){
38     scanf("%d%d",&n,&m);
39     while(m--){
40         int x,y;
41         scanf("%d%d",&x,&y);
42         g[x].push_back(y);///有向图
43     }
44     for(int i=1;i<=n;i++){
45         if(!dfn[i]){
46             tot=0;///图可能未连通
47             tarjan(i);
48         }
49     }
50     for(int i=1;i<=n;i++){
51         for(int j=0;j<g[i].size();j++){
52             if(belong[i]!=belong[g[i][j]]){///有连通但是属于不同连通分量使得出度+1
53                 du[belong[i]]++;
54             }
55         }
56     }
57     int flag=0,w;
58     for(int i=1;i<=tag;i++){
59         if(du[i]==0){
60             if(flag==0){
61                 flag=1;
62                 w=i;///出度为0的强连通分量的编号
63             }
64             else{
65                 flag=2;///出现多个出度为0的强连通分量时没有明星奶牛
66                 break;
67             }
68         }
69     }
70     if(flag==0||flag==2) printf("0
");
71     else{
72         int cnt=0;
73         for(int i=1;i<=n;i++){
74             if(belong[i]==w){
75                 cnt++;
76             }
77         }
78         printf("%d
",cnt);
79     }
80 }