2015
04-16

# The Social Network

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.

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.

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 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.

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

Case 1:
xhmz
yingying
digua
digua tangjiejie yingying
hongshu lcy zt
xmm
hongshu
huaxianzi
hongshu huaxianzi
-
-

http://acm.hdu.edu.cn/showproblem.php?pid=4039

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

const int N=2010;
int n, q, up, num;
char s[20], s1[20];
struct trie
{
int a[26];
int num;
void init()
{
memset(a, -1, sizeof(a));
num = -1;
}
} t[10000];
vector<int> a[N];
vector<int>::iterator it, it1;
int cnt[N], flag[N], flag1;
struct node
{
int i;
char s[16];
} ss[N], ss1[N];

inline int insert(char *s)
{
int p=0;
while(*s)
{
if(t[p].a[*s-'a']==-1)
{
t[up].init();
t[p].a[*s-'a'] = up++;
}
p = t[p].a[*s-'a'];
s++;
}
if(t[p].num==-1)
{
t[p].num = num++;
flag1 = 1;
}
return t[p].num;
}
inline int query(char *s)
{
int p=0;
while(*s)
{
if(t[p].a[*s-'a']==-1)
return -1;
p = t[p].a[*s-'a'];
s++;
}
return t[p].num;
}
int cmp(const node &a, const node &b)
{
return strcmp(a.s, b.s)<0;
}

int main()
{
int i, j, cas, cas1, x, y, mx;

scanf("%d", &cas);
for(cas1=1; cas1<=cas; cas1++)
{
scanf("%d%d%d", &n, &q);
t[0].init();
up = num = 1;
for(i=1; i<=n; i++)
{
scanf("%s %s", s, s1);
flag1 = 0;
x = insert(s);
if(flag1==1)
strcpy(ss[x].s, s);
flag1 = 0;
y = insert(s1);
if(flag1==1)
strcpy(ss[y].s, s1);
a[x].push_back(y);
a[y].push_back(x);
}
printf("Case %d:\n", cas1);
while(q--)
{
scanf("%s", s);
for(i=1; i<num; i++)
cnt[i] = 0;
x = query(s);
mx = 0;
for(i=1; i<num; i++)
flag[i] = 0;
flag[x] = 1;
for(it=a[x].begin(); it!=a[x].end(); it++)
flag[*it] = 1;
for(it=a[x].begin(); it!=a[x].end(); it++)
{
y = *it;
for(it1=a[y].begin(); it1!=a[y].end(); it1++)
{
if(flag[*it1]==0)
{
cnt[*it1]++;
if(cnt[*it1]>mx)
mx = cnt[*it1];
}
}
}
if(mx==0)
{
printf("-\n");
continue;
}
up = 0;
for(i=1; i<num; i++)
{
if(cnt[i]==mx)
{
strcpy(ss1[up].s, ss[i].s);
up++;
}
}
sort(ss1, ss1+up, cmp);

printf("%s", ss1[0].s);
for(i=1; i<up; i++)
printf(" %s", ss1[i].s);
printf("\n");
}

for(i=1; i<num; i++)
while(!a[i].empty())
a[i].pop_back();
}

return 0;
}

1. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的

2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

3. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。