题目描述

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

牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你

算出有多少头奶牛可以当明星。

输入输出格式

输入格式：

 

 第一行：两个用空格分开的整数：N和M

 第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B

 

输出格式：

 

 第一行：单独一个整数，表示明星奶牛的数量

 

输入输出样例

输入样例#1：

3 31 22 12 3

输出样例#1：

1

说明

只有 3 号奶牛可以做明星

【数据范围】

10%的数据N<=20, M<=50

30%的数据N<=1000,M<=20000

70%的数据N<=5000,M<=50000

100%的数据N<=10000,M<=50000

 

tarjan缩点，

当一个点的出度为0是，他们是明星、

当有两个及以上的店出度为0是，他们不可能相互喜欢，所以没有明星。

这里有个小技巧，

我们反向加边，就把求出度的问题改为了求入度的问题

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 using namespace std; 9 const int MAXN=500001; 10 static void read(int &n) 11 { 12 char c='+';int x=0;bool flag=0; 13 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 14 while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();} 15 flag==1?n=-x:n=x; 16 } 17 struct node 18 { 19 int u,v,nxt; 20 }edge[MAXN]; 21 int head[MAXN]; 22 int num=1; 23 void add_edge(int x,int y) 24 { 25 edge[num].u=x; 26 edge[num].v=y; 27 edge[num].nxt=head[x]; 28 head[x]=num++; 29 } 30 int dfn[MAXN]; 31 int low[MAXN]; 32 int tot=0; 33 int vis[MAXN]; 34 int color[MAXN]; 35 int colornum; 36 int happen[MAXN]; 37 stack
            
             s; 38 void tarjan(int now) 39 { 40 dfn[now]=low[now]=++tot; 41 vis[now]=1; 42 s.push(now); 43 for(int i=head[now];i!=-1;i=edge[i].nxt) 44 { 45 if(!dfn[edge[i].v]) 46 { 47 tarjan(edge[i].v); 48 low[now]=min(low[now],low[edge[i].v]); 49 } 50 else if(vis[edge[i].v])// 公共祖先 51 { 52 low[now]=min(low[now],dfn[edge[i].v]); 53 } 54 } 55 if(dfn[now]==low[now])// root 56 { 57 colornum++; 58 while(now!=s.top()) 59 { 60 if(!color[s.top()]) 61 color[s.top()]=colornum; 62 happen[color[s.top()]]++; 63 vis[s.top()]=0; 64 s.pop(); 65 } 66 if(!color[s.top()]) 67 color[s.top()]=colornum; 68 happen[color[s.top()]]++; 69 vis[s.top()]=0; 70 s.pop(); 71 } 72 } 73 int main() 74 { 75 // freopen("cow.in","r",stdin); 76 // freopen("cow.out","w",stdout); 77 int n,m; 78 memset(head,-1,sizeof(head)); 79 read(n);read(m); 80 for(int i=1;i<=m;i++) 81 { 82 int x,y; 83 read(x);read(y); 84 add_edge(y,x); 85 } 86 87 for(int i=1;i<=n;i++) 88 if(!dfn[i]) 89 tarjan(i); 90 // for(int i=1;i<=n;i++) 91 // happen[color[i]]++; 92 memset(vis,0,sizeof(vis)); 93 for(int i=1;i<=n;i++) 94 for(int j=head[i];j!=-1;j=edge[j].nxt) 95 if(color[edge[j].u]!=color[edge[j].v]) 96 vis[color[edge[j].v]]++; 97 int ans=0; 98 for(int i=1;i<=colornum;i++) 99 if(!vis[i])100 {101 if(ans)102 {103 printf("0\n");104 return 0;105 }106 else ans=happen[i];107 }108 printf("%d",ans);109 return 0;110 }