题意分析

题目描述了一个牛群中奶牛之间的 “受欢迎” 关系，这种关系具有传递性。例如，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么 A 也会认为 C 受欢迎。我们需要找出被所有其他奶牛都认为受欢迎的奶牛数量。 关键点： 传递性：如果 A 认为 B 受欢迎，B 认为 C 受欢迎，则 A 自动认为 C 受欢迎。

目标：统计被所有其他奶牛直接或间接认为受欢迎的奶牛数量。

解题思路

问题转化：

每头奶牛视为一个节点，每个有序对 (A, B) 表示从 A 到 B 的一条有向边。

若存在一头奶牛 C，所有其他奶牛都能通过有向边到达 C，则 C 是被所有奶牛认为受欢迎的。

强连通分量（SCC）：

若两头奶牛 A 和 B 互相认为对方受欢迎，则它们属于同一个强连通分量（SCC）。

在同一个 SCC 中的奶牛互相可达，因此它们要么全部被其他奶牛认为受欢迎，要么都不被。

缩点与 DAG：

将每个 SCC 缩成一个点，形成一个有向无环图（DAG）。

若存在一个 SCC 是 DAG 中的唯一出度为 0 的节点，则该 SCC 中的所有奶牛均被其他所有奶牛认为受欢迎。

算法步骤：

Tarjan 算法：找出所有 SCC 并缩点。

统计出度：在缩点后的 DAG 中，统计每个 SCC 的出度。

唯一性检查：若恰好存在一个出度为 0 的 SCC，则其大小即为答案；否则无解。

复杂度：

时间复杂度：O (N + M)，Tarjan 算法可在线性时间内找到所有 SCC。

代码

#include<iostream>
#include<math.h>
#include<stdio.h> // 添加标准输入输出头文件
#include<stdlib.h> // 添加标准库头文件，包含malloc等函数
#include<string.h> // 添加字符串处理头文件，包含memset函数
using namespace std;
bool visit[10000];
typedef struct enode{
   int adj; 
   struct enode *next;        
}enode;
typedef struct vnode{
    enode *find;
}vnode;
typedef vnode List[10000];
typedef struct graphic{
    List list;
    int n,e;       
}graphic;
typedef struct Edge{
    int s, e;
} Edge;
Edge E[100000];
int order[10000],id[10000],in[10000];
int cnt;
void create(graphic *g,graphic *g1){
    scanf("%d %d",&g->n,&g->e);
    g1->n=g->n; g1->e=g->e;   
    for(int i=0;i<g->n;i++){
        g->list[i].find=NULL;
        g1->list[i].find=NULL;
    }   
    for(int i=0;i<g->e;i++){
        enode *p=(enode *)malloc(sizeof(enode));
        int k,m;   
        scanf("%d%d",&k,&m);
        k--; m--;
        E[i].s=k; E[i].e=m;
        p->adj=m; p->next=g->list[k].find;
        g->list[k].find=p;
        p=(enode *)malloc(sizeof(enode));
        p->adj=k;  p->next=g1->list[m].find;
        g1->list[m].find=p;    
    }
}
void dfs1(graphic *g,int i){
       enode *p=g->list[i].find;;
       visit[i]=true;
       while(p) {
           if(!visit[p->adj]) dfs1(g,p->adj);
           p=p->next;        
       }  
       order[cnt++]=i;
}
void dfs(graphic *g,int i){
       enode *p=g->list[i].find;;
       visit[i]=true;
       id[i]=cnt;
       while(p) {
           if(!visit[p->adj])dfs(g,p->adj);
           p=p->next;        
       }  
}
void dfs2(graphic *g,int i){
     enode *p=g->list[i].find;
     visit[i]=true;
     while(p){
          if(id[i]!=id[p->adj]) in[i]++;
          if(!visit[p->adj]) dfs(g,p->adj);
          p=p->next;         
     }
}
int main(){
   int pos;
   graphic *g=(graphic *)malloc(sizeof(graphic));
   graphic *g1=(graphic *)malloc(sizeof(graphic));
   create(g,g1);
   memset(visit,0,sizeof(visit)); cnt=0;
   for(int i=0;i<g->n;i++)
       if(!visit[i]) dfs1(g1,i);
   memset(visit,0,sizeof(visit)); cnt=0;
   for(int i=g->n-1;i>=0;i--){
       if(!visit[order[i]]){ 
            dfs(g,order[i]);
            cnt++;        
       }
   }
   int s,e;
   for (int i = 0; i < g->e; i++){ //一个部落能通往其他部落则为1 
        s = id[E[i].s];
        e = id[E[i].e];
        if (s != e)  in[s]++;
    }
    int scnt = cnt;
    cnt = 0;
    for(int i = 0; i < scnt; i++){ //如果强连通则只有一个为0 
        if (in[i] == 0){
            pos = i; //保存了最后的那个部落 
            cnt++;
        }
    }
    if (cnt != 1) printf("0\n");
    else{
        cnt = 0;
        for (int i = 0; i < g->n; i++)
            if (in[id[i]] == pos) //求出最后那个部落的人数 
                cnt++;
        printf("%d\n", cnt);
    }
   system("pause");
   return 0;
}
```

```