The Social Network
Time Limit: 3000/2000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1795 Accepted Submission(s): 555
Problem Description
The social network system (SNS) helps people to keep connecting with their friends. Every user in SNS has a friends list. The user can read news posted by the users in his friends list. Friend relation is symmetric - if A is a friend of B, B is always a friend
of A.
of A.
Another important function in SNS is friend recommendation. One effective way to recommend friends is recommend by mutual friends. A mutual friend between two users A and B, is a user who is a friend of both A and B. A user can not be a friend of himself. For
a specific user A, the system will recommend the user who is not himself or his friend, and has mutual friends with A. If more than one such user exists, recommend the one has most mutual friends with A. If still a tie exists, output all of them.
Input
The first line is a integer T (T≤100), the number of test case.
The beginning of each test case is two integers N and Q, the number of friend relationship and the number of query. 1 ≤ N, Q ≤ 1000
The following N lines each contain two different names separated by a single space. Each name consisted by only lowercase letters, and its length is less than or equal to 15. This means the two users are friends. No friend relationship will be given more than
once.
The following Q lines each describe a query. Each line contain one user name. The data guarantee that this name appears at least once in above N lines.
The beginning of each test case is two integers N and Q, the number of friend relationship and the number of query. 1 ≤ N, Q ≤ 1000
The following N lines each contain two different names separated by a single space. Each name consisted by only lowercase letters, and its length is less than or equal to 15. This means the two users are friends. No friend relationship will be given more than
once.
The following Q lines each describe a query. Each line contain one user name. The data guarantee that this name appears at least once in above N lines.
Output
For each case, you should output one line containing “Case k: ” first, where k indicates the case number and counts from one. Then for each query, output one line, contains one or more names of recommended friends, separate by a single space, sorted by alphabetical
order. If no persons can be recommended, output one line contains “-”.
order. If no persons can be recommended, output one line contains “-”.
Sample Input
1 10 11 hongshu digua yingying hongshu xmm hongshu huaxianzi xmm tangjiejie huaxianzi xhmz yingying digua xhmz zt tangjiejie xmm lcy notonlysuccess ljq hongshu digua yingying xmm huaxianzi tangjiejie xhmz zt lcy notonlysuccess ljq
Sample Output
Case 1: xhmz yingying digua digua tangjiejie yingying hongshu lcy zt xmm hongshu huaxianzi hongshu huaxianzi - -
Source
概括题意：找不是自己朋友的朋友的朋友。
1：用map给每个姓名一个数字映射。
2：姓名上限要开2*MAX，可能是每对姓名都不相同。
3：其他就是BFS的搜索的，尽可能优化吧。
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
#define MAX 2005
map<string,int> mat;//姓名数字映射
vector<int> num[MAX];//某人的朋友
string name[MAX],out[MAX];//name存姓名，out存输出的姓名
int countx[MAX];//计数
bool flag[MAX];//是否是查找人的朋友
int cnt,u,v;
int main()
{
int T,N,Q;
scanf("%d",&T);
for(int ti=1;ti<=T;++ti)
{
char s1[25],s2[25];
string si;
cnt=0;
scanf("%d%d",&N,&Q);
for(int i=0;i<N;++i)
num[i].clear();
mat.clear();
for(;N--;)
{
scanf("%s %s",s1,s2);
si=string(s1);
if(mat.count(si))
u=mat.find(si)->second;
else
{
u=cnt;
name[cnt]=si;
mat.insert(make_pair(si,cnt++));
}
si=string(s2);
if(mat.count(si))
v=mat.find(si)->second;
else
{
v=cnt;
name[cnt]=si;
mat.insert(make_pair(si,cnt++));
}
num[u].push_back(v);
num[v].push_back(u);
}
printf("Case %d:\n",ti);
for(;Q--;)
{
scanf("%s",s1);
si=string(s1);
if(!mat.count(si)) continue;
memset(countx,0,sizeof(countx));
memset(flag,false,sizeof(flag));
int tmp=mat.find(si)->second;
for(int i=0;i<num[tmp].size();++i)
flag[num[tmp][i]]=true;
for(int i=0;i<cnt;++i)
if(flag[i])
for(int j=0;j<num[i].size();++j)
countx[num[i][j]]++;
int maxx=0;
for(int i=0;i<cnt;++i)
if(countx[i]>maxx&&(!flag[i])&&(i!=tmp))
maxx=countx[i];
if(maxx==0)
{
printf("-\n");
continue;
}
int tmt=0;
for(int i=0;i<cnt;++i)
if(countx[i]==maxx&&(!flag[i])&&(i!=tmp))
out[tmt++]=name[i];
sort(out,out+tmt);
for(int i=0;i<tmt;++i)
{
if(i!=0) printf(" ");
printf("%s",out[i].c_str());
}
printf("\n");
}
}
return 0;
}