题目
Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well.
According to Wikipedia, opinion leadership is leadership by an active media user who interprets the meaning of media messages or content for lower-end media users. Typically opinion leaders are held in high esteem by those who accept their opinions.
To be more specific, let's define an opinion leader index OLI to be N
in
/N
out
, where N
in
is the number of one's followers and N
out
is the number of users that one follows on Weibo. Then for any given threshold T, we call those users whose OLI is at least T the opinion leaders.
Some of the opinion leaders may follow each other. An opinion leader who has the most number of other opinion leaders following him/her is defined to be the leader of the opinion leaders. Your job is to find those leaders of the opinion leaders.
输入格式
Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤10
4
), the number of users; and T (≤100), the threshold for OLI. Hence it is assumed that all the users are numbered from 1 to N, and those users whose OLI is at least T is the opinion leaders.
Then N lines follow, each in the format:
M[i] user_list[i]
where M[i] (≤100) is the total number of people that user[i] follows and is always positive; and user_list[i] is a list of the indices of the M[i] users that are followed by user[i]. It is guaranteed that no one can follow oneself, and all the indices in a user_list[i] are distinct. All the numbers are separated by a space.
输出格式
Print in one line all the leaders of the opinion leaders, in ascending order of their indices.
It is guranteed that there is at least one ouput. All the numbers must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.
输入示例
10 3
3 9 3 8
2 1 3
2 9 7
3 2 7 5
3 6 3 7
2 7 3
1 2
2 3 9
1 10
1 3
输出示例
7 9
代码
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 10010;
struct node
{
int ol = -1, follows = 0;
};
vector<node> user(maxn);
vector<vector<int>> fan(maxn);
vector<int> ans;
int n, t, follow, f, maxc = 0;
int main()
{
cin >> n >> t;
for (int i = 1; i <= n; i++)
{
cin >> follow;
user[i].follows = follow;
for (int j = 0; j < follow; j++)
{
cin >> f;
fan[f].emplace_back(i);
}
}
for (int i = 1; i <= n; i++)
{
if (fan[i].size() / user[i].follows >= t)
{
user[i].ol = 1;
}
}
for (int i = 1; i <= n; i++)
{
if (user[i].ol == 1)
{
int cnt = 0;
for (int fa : fan[i])
{
if (user[fa].ol == 1) cnt++;
}
if (cnt > maxc)
{
maxc = cnt;
ans.clear();
ans.emplace_back(i);
}
else if (cnt == maxc)
{
ans.emplace_back(i);
}
}
}
for (int i = 0; i < ans.size(); i++)
{
if (i != 0) cout << ' ';
cout << ans[i];
}
}