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

$$POPULAR$$

题目链接：

题目

每头牛都有一个梦想：成为一个群体中最受欢迎的名牛！在一个有$N$头牛的牛群中，给你$M$个二元组$(A,B)$,表示$A$认为$B$是受欢迎的。既然受欢迎是可传递的，那么如果$A$认为$B$受欢迎，$B$又认为$C$受欢迎,则$A$也会认为$C$是受欢迎的，哪怕这不是十分明确的规定。你的任务是计算被所有其它的牛都喜欢的牛的个数。

输入

第一行，两个数，$N$和$M$。第$2～M+1$行，每行两个数，$A$和$B$，表示$A$认为$B$是受欢迎的。

输出

一个数，被其他所有奶牛认为受欢迎的奶牛头数。

样例输入

3 31 22 12 3

样例输出

1

样例解释

$3$号奶牛是唯一被所有其他奶牛认为有名的。

数据范围

$1<=N<=10,000$

思路

这道题就是一道$dfs$。

代码

#include
   
    #include
    
     using namespace std;struct note {   	int to, next;}a[50001];int n, m, x, y, k, le[50001], count[50001], ans;bool in[50001];void dfs(int now) {   //dfs	in[now] = 1;//标记	for (int i = le[now]; i; i = a[i].next)		if (!in[a[i].to]) {   			count[a[i].to]++;//记录			dfs(a[i].to);		}		}int main() {   	scanf("%d %d", &n, &m);//读入	for (int i = 1; i <= m; i++) {   		scanf("%d %d", &x, &y);//读入		a[++k] = (note){   y, le[x]}; le[x] = k;//邻接表储存	}		for (int i = 1; i <= n; i++) {   		memset(in, 0, sizeof(in));//初始化		dfs(i);//dfs	}		for (int i = 1; i <= n; i++)		if (count[i] == n - 1) ans ++;//记录	printf("%d", ans);//输出		return 0;}