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

 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\n");
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\n",cnt);
79     }
80 }