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.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: $N$ ($\le 10^4$), the number of users; and $T$ ($\le 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]
($\le 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.
Output Specification:
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.
Sample Input:
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
Sample Output:
7 9
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
int main()
{
int n;
int t;
cin >> n >> t;
vector out(n + 1, 0);
vector in(n + 1, 0);
vector<unordered_set<int>> following(n + 1);
unordered_map<int, int> kols;
for (int i = 1; i <= n; i++)
{
int m;
cin >> m;
out[i] += m;
while (m-- != 0)
{
int u;
cin >> u;
in[u]++;
following[i].insert(u);
}
}
for (int i = 1; i <= n; i++)
{
if (out[i] == 0 || in[i] / following[i].size() >= t)
{
if (!kols.contains(i))
{
kols[i] = 0;
}
}
}
for (const auto &kol : kols)
{
for (const auto &fo : following[kol.first])
{
if (kols.contains(fo))
{
kols[fo]++;
}
}
}
int maximum = 0;
for (auto &kv : kols)
{
maximum = max(maximum, kv.second);
}
vector<int> ans;
for (auto &kv : kols)
{
if (kv.second == maximum)
{
ans.emplace_back(kv.first);
}
}
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++)
{
cout << ans[i];
if (i != ans.size() - 1)
{
cout << ' ';
}
}
return 0;
}