好友推荐策略

描述

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

任务为：
不使用STL和Mapreduce,
对设定的m值，给定一组用户及各自好友列表，对这一组用户，反复自动应用上述好友推荐策略后（假设每次推荐都被采纳），求指定用户的最终好友列表。
要求算法复杂度不高于O（n^2）,用户总数规格不受限；

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

分析

HASH. 将好友数小的那个人的朋友插入HASH表中，然后遍历另外一个人的好友，在HASH表中进行查询。

Code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2000;

const int mod = 1997;

int AF[maxn];
int BF[maxn];

struct HASH{
int a[maxn];
int head[maxn];
int next[maxn];
int sz;
void init(){
memset(head,-1,sizeof(head));
        sz=0;
    }
bool find(int val){
int tmp = (val%mod+mod)%mod;
for(int i=head[tmp];i!=-1;i=next[i]){
if(val==a[i])
return true;
        }
return false;
    }
void insert(int val){
int tmp = (val%mod+mod)%mod;
if(find(val))
return;
        a[sz]=val;
        next[sz]=head[tmp];
        head[tmp]=sz++;
    }
}h;

int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)){
for(int i=0;i<n;i++){
scanf("%d",AF+i);
        }
for(int i=0;i<m;i++){
scanf("%d",BF+i);
        }
int commonfriend = 0;
        h.init();
if(n<m){
for(int i=0;i<n;i++){
                h.insert(AF[i]);
            }
for(int i=0;i<m;i++){
if(h.find(BF[i]))
                    commonfriend++;
            }
        }
else{
for(int i=0;i<m;i++){
                h.insert(BF[i]);
            }
for(int i=0;i<n;i++){
if(h.find(AF[i]))
                    commonfriend++;
            }
        }
printf("ans = %d\n",commonfriend);
    }
return 0;
}

拓展

社交网络中的好友推荐方法研究
微博好友推荐算法-SALSA