华为机试题 好友关系管理

时间:2021-11-11 18:51:41

好友关系管理
描述:

现有一个社交网站,其好友推荐策略为:用户A和用户B不是好友,当二人的共同好友数量超过好友推荐阈值m时,就向AB分别推荐为彼此好友。 

本题任务为:对设定的m值,给定一组用户及各自好友列表,对这一组用户,反复自动应用上述好友推荐策略后(假设每次推荐都被采纳),求指定用户的最终好友列表。 

注:好友关系是双向的,即:如果用户A是用户B的好友,那么用户B一定也是用户A的好友。 

 

写一个程序,在社交网络中实现:

1)初始化社交网络 

2)创建用户 

3)增加指定两个用户之间的好友关系

4)反复自动应用好友推荐策略后,获取某个用户的好友数量 

5)反复自动应用好友推荐策略后,判断某两个用户间是否存在好友关系 

    

说明:

1、一个用户有且只有一个名字,且不存在重名 

2、自己和自己不存在好友关系 

3、用户名字大小写敏感 

4、用户名字字符串长度范围为[1..20]

5、用户总数小于100个

 

运行时间限制: 无限制
内存限制: 无限制
输入:

五个整数,好友推荐阈值P创建用户数量m,增加指定两个用户之间的好友关系数量M,查询某个用户的好友数量n,查询指定两个用户是否是好友N字符串,每个数据一行,按到上面的顺序依次输入数据,共m+M+n+N行字符串

字符串,每个一行,共m+M+n+N行字符串

 

输出:

输出用户的好友数量,共n个,每个一行;如果用户不存在,输出-1,否则输出好友数量。样例中的用户Jack、Peter、Tom的好友数量都是2个。

输出指定两个用户是否是好友,共N个,每个一行,如果是输出0,否则输出-1。样例中的用户Jack与Peter、Peter与Tom、Jack与Tom都是好友关系,所有输出0。

 

样例输入:
2 3 3 3 3 //好友推荐阈值2,用户数量为3,增加知道两个用户之间的好友关系数量M,
 //查询某个用户的好友数量3,查询指定两个用户是否是好友N字符串
 Jack 
 Peter 
 Tom //输入了三个用户
 Jack Peter 
 Peter Tom 
 Jack Tom //增加了三个好友关系
 Jack
 Peter 
 Tom //查询了这三个用户的好友数量
 Jack Peter 
 Peter Tom 
 Jack Tom //查询了这三个好友关系是否存在
 样例输出: 

        
样例输出:
2 //Jack几个好友,这里就用到了阈值2 //Peter几个好友2 0 //Jack Peter是否好友0 //Peter Tom是否好友0 //Jack Tom是否好友



#include<iostream>
#include<string>
#include<map>
using namespace std;

const int maxn = 1010;
bool mp[maxn][maxn];// mp[i][j] 表示 i 和 j 是否为好友
int num[maxn];// num[i] 表示第 i 个人有多少个好友

int main(){
int P, m, M, n, N, i, j, k;
scanf("%d %d %d %d %d", &P, &n, &N, &m, &M);
string str1, str2;
map<string, int> id;// 名字转化为id
for(i = 0; i < m; ++i){
cin >> str1;
id[str1] = i;
}
for(i = 0; i < M; ++i){
cin >> str1 >> str2;
mp[id[str1]][id[str2]] = mp[id[str2]][id[str1]] = 1;
}
bool flag = 1;// 表示是否会有新的好友对产生
int count;// 共同好友的个数
while(flag){
flag = 0;
for(i = 0; i < m; ++i){
for(j = i + 1; j < m; ++j){
if(mp[i][j]){
continue;
}
count = 0;
for(k = 0; k < m; ++k){
if(k == i || k == j){
continue;
}
if(mp[i][k] && mp[k][j]){
++count;
}
}
if(count > P){
mp[i][j] = mp[j][i] = 1;
flag = 1;// 有新的好友对产生,需要再次处理
}
}
}
}
// 统计每个人的好友个数
for(i = 0; i < m; ++i){
for(j = 0; j < m; ++j){
if(mp[i][j]){
++num[i];
}
}
}

for(i = 0; i < n; ++i){
cin >> str1;
printf("%d\n", num[id[str1]]);
}

for(i = 0; i < N; ++i){
cin >> str1 >> str2;
if(mp[id[str1]][id[str2]]){
printf("0\n");
}else{
printf("-1\n");
}
}
}