华为机试9月4号题解

你正在为一个社交网络平台开发好友推荐功能。

平台上有N个用户(每个用户使用1到N的整数编号)，同时系统中维护了用户之间的好友关系。

为了推荐新朋友，平台决定采用“共同好友数量"作为衡量两个用户之间相似度的标准。

系统根据输入用户编号K，输出与此用户K相似度最高的前L个用户ID来推荐给用户K。

相似度定义:两个用户非好友，两个用户的相似度为拥有的共同好友数(例如用户A和用户B，只有共同好友C和D，相似度=2)

输入

第一行包含四个整数 N，M 、K和L，分别表示用户的数量(N)，好友记录条数(M)、查询的用户编号(K)和推荐的好友数量(L)。接下来 M 行，每行包含两个整数编号X和Y，表示编号为X和Y用户是好友。

1.输入格式都是标准的，无需考虑输出异常场景(不会包含用户和自己是好友的输入，例如11)

2.用户数不超过1024，用户编码最大1024

3.好友记录数不超过10240

输出

根据输入K和L，输出和用户K相似度最高的L个用户编码。

1.输出相似度最高的前L个用户编码，按照相似度从高到低排序

2.如果有相似度相同的可能好友，按照用户编号从小到大排序

3.如果推荐的好友个效不足L个，则推荐与用户K无无共同好友关系的用户(陌生人)作为可能好友，如果推荐仍不满足L个用户，剩余推荐用户编码使用0来占位

测试用例

6 7 3 2
1 2
1 3
2 3
3 4
3 5
4 5
5 6

6 0

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

int main() {
    int N, M, K, L;
    std::cin >> N >> M >> K >> L;

    // Create a list of sets to store friends
    std::vector<std::set<int>> friends(N + 1);

    // Read the pairs of friends and populate the sets
    for (int i = 0; i < M; ++i) {
        int a, b;
        std::cin >> a >> b;
        friends[a].insert(b);
        friends[b].insert(a);
    }

    std::vector<std::pair<int, int>> res; // pairs存储 first 共同好友数，second 用户

    // Find potential friends
    for (int i = 1; i <= N; ++i) {
        if (friends[K].find(i) == friends[K].end() && i != K) {
            // 共同好友数
            int mutual_count = 0;
            for (int friend_of_i : friends[i]) {
                if (friends[K].find(friend_of_i) != friends[K].end()) {
                    ++mutual_count;
                }
            }
            res.push_back({ mutual_count, i });
        }
    }

    // Sort results，按first降序排序
    std::sort(res.begin(), res.end());
    //反转后升序
    std::reverse(res.begin(), res.end());

    std::vector<int> ans; // Final result

    // Extract the top L results
    int m = res.size();
    for (int i = 0; i < m && i < L; i++) {
        ans.push_back(res[i].second);
    }

    // Fill with zeroes if less than L results
    while (ans.size() < L) {
        ans.push_back(0);
    }

    // Print the results
    for (int i = 0; i < ans.size(); ++i) {
        std::cout << ans[i] << (i < ans.size() - 1 ? ' ' : '\n');
    }

    return 0;
}