114514

#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

class SocialNetwork {
private:
// 用户 -> 好友集合
map<string, set<string>> friendships;

public:
// 添加用户
　　void addUser(const string& username) {
　　　　friendships.emplace(username, set<string>{});
　　}

// 建立好友关系
　　bool addFriendship(const string& user1, const string& user2) {
　　　　if (friendships.count(user1) && friendships.count(user2)) {
　　　　　　friendships[user1].insert(user2);
　　　　　　friendships[user2].insert(user1);
　　　　　　return true;
　　　　}
　　return false;
}

// 获取共同好友
set<string> getMutualFriends(const string& user1, const string& user2) const {
set<string> mutual;

if (!friendships.count(user1) || !friendships.count(user2)) {
　　return mutual;
}

const set<string>& friends1 = friendships.at(user1);
const set<string>& friends2 = friendships.at(user2);

set_intersection(friends1.begin(), friends1.end(),
friends2.begin(), friends2.end(),
inserter(mutual, mutual.begin()));

return mutual;
}

// 好友推荐算法
vector<pair<string, int>> getFriendRecommendations(const string& username) const {
　　if (!friendships.count(username)) return {};

　　map<string, int> recommendationScores;
　　const set<string>& userFriends = friendships.at(username);

　　// 基于共同好友的推荐算法
　　for (const string& friendName : userFriends) {
　　　　for (const string& friendOfFriend : friendships.at(friendName)) {
　　　　　　// 排除已经是好友的和自己
　　　　　　if (friendOfFriend != username &&
　　　　　　　　userFriends.count(friendOfFriend) == 0) {
　　　　　　　　　　recommendationScores[friendOfFriend]++;
　　　　　　　　}
　　　　　　}
}

// 转换为向量并排序
vector<pair<string, int>> recommendations(
　　recommendationScores.begin(), recommendationScores.end());

　　sort(recommendations.begin(), recommendations.end(),
　　[](const auto& a, const auto& b) {
　　　　return a.second > b.second; // 按分数降序
　　});

　　return recommendations;
}

// 显示网络状态
void displayNetwork() const {
　　cout << "=== 社交网络状态 ===" << endl;
　　cout << "用户数量: " << friendships.size() << endl;

　　for (const auto& [user, friends] : friendships) {
　　　　cout << "\n" << user << " 的好友 (" << friends.size() << "): ";
　　　　for (const string& friendName : friends) {
　　　　　　cout << friendName << " ";
　　　　}
　　}
　　cout << endl;
　　}
};

int main() {
　　SocialNetwork network;

　　// 添加用户
　　vector<string> users = {"Alice", "Bob", "Charlie", "David", "Eve", "Frank"};
　　for (const string& user : users) {
　　　　network.addUser(user);
　　}

　　// 建立好友关系

　　network.addFriendship("Alice", "Bob");
　　network.addFriendship("Alice", "Charlie");
　　network.addFriendship("Alice", "David");
　　network.addFriendship("Bob", "David");
　　network.addFriendship("Bob", "Eve");
　　network.addFriendship("Charlie", "Frank");
　　network.addFriendship("David", "Eve");
　　network.addFriendship("Eve", "Frank");

// 显示网络
　　network.displayNetwork();

// 测试共同好友
　　cout << "\n=== 共同好友分析 ===" << endl;
　　auto mutual = network.getMutualFriends("Alice", "Bob");
　　cout << "Alice 和 Bob 的共同好友: ";
　　for (const string& friendName : mutual) cout << friendName << " ";
　　cout << endl;

// 好友推荐
　　cout << "\n=== 好友推荐 ===" << endl;
　　auto recommendations = network.getFriendRecommendations("Alice");
　　cout << "给 Alice 的推荐:" << endl;
　　for (const auto& [user, score] : recommendations) {
　　　　cout << " " << user << " (共同好友数: " << score << ")" << endl;
　　}

// 性能分析
　　cout << "\n=== 性能分析 ===" << endl;
　　cout << "算法复杂度分析:" << endl;
　　cout << "共同好友查找: O(min(n, m)) - 使用set_intersection" << endl;
　　cout << "好友推荐: O(d2) - d是平均好友数" << endl;
　　cout << "空间复杂度: O(n + e) - n用户数, e边数" << endl;

return 0;
}