华为机试题 好友关系管理

好友关系管理
描述:	现有一个社交网站，其好友推荐策略为：用户A和用户B不是好友，当二人的共同好友数量超过好友推荐阈值m时，就向A和B分别推荐为彼此好友。  本题任务为：对设定的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");
}
}
}