今日头条笔试题 之 寻找抖音红人

题目：

抖音有N个用户，有M个关注对（A, B），表示A关注了B。用户的关注具有传递性：假设A关注了B，B关注了C，则认为A间接关注了C。如果一个用户被所有其他用户关注，则认为这个用户是一个抖音红人。要求：输入N、M的值以及M个关注对，找出一共有多少个抖音红人。

例：

输入：

3

3

1 2 2 1 2 3

输出：

1

解释：3被2直接关注，被1间接关注。

题目分析：

可以采用一个N*N的矩阵来记录各个用户被其他用户关注的情况。每读入一个关注对（A, B），除了让A关注B，让关注A的也关注B，让关注关注A的也关注B...这个过程可以采用递归实现。

代码实现：

#include 
#include using namespace std;int N;
int M;
vector> guanzhu;// a关注了b，让关注a的也关注b
void update(int a, int b)
{for (int i = 0; i < N; i++)		// 遍历每个用户{if (guanzhu[a][i] && !guanzhu[b][i])			// 关注了a，还没关注b{guanzhu[b][i] = 1;			// 关注bupdate(i, b);				// 让关注i的也关注b}}
}void main()
{cin >> N;cin >> M;// 初始化矩阵for (int i = 0; i < N; i++){vector row(N, 0);guanzhu.push_back(row);}int a, b;for (int i = 0; i < M; i++){cin >> a >> b;a--; b--;guanzhu[b][a] = 1;update(a, b);}// 数总共几个红人int cnt = 0;for (int i = 0; i < N; i++){int gz = 1;for (int j = 0; j < N; j++){if (!guanzhu[i][j] && i != j)			// 除了自己{gz = 0;break;}}if (gz)cnt++;}cout << cnt << endl;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！