Untitled

#include <vector>
#include <set>
#include <unordered_map>
using namespace std;

vector<int> getRecommendedFriends(int n, vector<vector<int>>& friendships) {
    // Create an adjacency list to store friends of each user
    vector<set<int>> adj(n);
    for (const auto& f : friendships) {
        int i = f[0], j = f[1];
        adj[i].insert(j);
        adj[j].insert(i);
    }

    // Create a list of unordered_maps to count common friends
    vector<unordered_map<int, int>> common(n);

    // Calculate the number of common friends for each pair of non-friends
    for (const auto& f : friendships) {
        int u1 = f[0], u2 = f[1];
        for (int u3 : adj[u2]) {
            if (u3 != u1 && adj[u1].find(u3) == adj[u1].end()) {
                common[u1][u3]++;
            }
        }
        for (int u3 : adj[u1]) {
            if (u3 != u2 && adj[u2].find(u3) == adj[u2].end()) {
                common[u2][u3]++;
            }
        }
    }

    // Prepare the result array
    vector<int> r(n, -1);

    for (int i = 0; i < n; ++i) {
        // Nobody has common friend with user i.
        if (common[i].empty()) {
            // This loop will execute at most 15 times.
            for (int j = 0; j < n; ++j) {
                if (j != i && adj[i].find(j) == adj[i].end()) {
                    r[i] = j;
                    break;
                }
            }
        } else {
            int c = -1;
            for (const auto& p : common[i]) {
                int user = p.first, num = p.second;
                if (c < num || (c == num && (r[i] == -1 || user < r[i]))) {
                    r[i] = user;
                    c = num;
                }
            }
        }
    }

    return r;
}

// Example usage
int main() {
    vector<vector<int>> friendships1 = {{0, 1}, {1, 2}, {2, 0}};
    vector<int> result1 = getRecommendedFriends(3, friendships1);
    // Expected output: [-1, -1, -1]
    for (int r : result1) {
        printf("%d ", r);
    }
    printf("\n");

    vector<vector<int>> friendships2 = {{0, 1}, {0, 2}};
    vector<int> result2 = getRecommendedFriends(3, friendships2);
    // Expected output: [-1, 2, 1]
    for (int r : result2) {
        printf("%d ", r);
    }
    printf("\n");

    vector<vector<int>> friendships3 = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
    vector<int> result3 = getRecommendedFriends(5, friendships3);
    // Expected output: [3, 2, 1, 0, 1]
    for (int r : result3) {
        printf("%d ", r);
    }
    printf("\n");

    return 0;
}