本文共 998 字，大约阅读时间需要 3 分钟。

题目描述：

给定一个N头牛的牛群，和M个关系（A，B），其中牛A认为牛B是红人，该关系具有传递性，所以A认为B是红人，B认为C是红人，则A也认为C是红人，现在要求被所有牛都认为是红人的牛的数量。

思路：

  可以把这个题看做是强连通分量的题目来做，其中若一些牛被其他所有的牛都认为是红人，则他们肯定属于同一个强连通分量里面（因为他们彼此都认为是红人）而且在所有的关系里面最多有一个强连通分量，因为他们只要是被其他人都认作是红人，他们肯定属于同一个强连通分量里面，所以此时我们只需要找出那个强连通分量，然后看看是不是和其他牛可达即可。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN=10050;vector
        
          G[MAXN];//正向关系vector
         
           rG[MAXN];//反向关系vector
          
            vs;//记录每一个新开始的结点int vis[MAXN];//标记是否访问过int cmp[MAXN];//记录在第几个强连通分量里面void bfs(int x)//正向BFS{ vis[x]=1; for(int i=0; i
           
            =0; i--) { if(!vis[vs[i]]) rbfs(vs[i],k++); } int num=0,u; for(int i=1; i<=n; i++) { if(cmp[i]==k-1)//因为最多只有一个强连通分量，所以如果这个强连通分量存在的话，也一定是在第（k-1）个， { u=i;//因为在访问到这个强连通分量的时候，他可以把剩下所有没访问到的结点都访问过，因为其他点到这个强连通分量都是可达的。 num++; } } memset(vis,0,sizeof(vis)); rbfs(u,1); for(int i=1; i<=n; i++) { if(!vis[i]) { num=0; break; } } printf("%d\n",num); return 0;}
           
          
         
        
       
      
     
    
   

转载地址：http://mygsi.baihongyu.com/