题目链接

我朋友的朋友不是我的朋友

题目描述

在一个社交圈中，有 位成员和 对朋友关系。每位成员的“社牛指数”定义为其直接认识的朋友数量。而“朋友平均社牛指数”则定义为其所有朋友的“社牛指数”的算术平均值。

如果一个成员的“社牛指数”大于其“朋友平均社牛指数”，则称该成员为“社牛”。

任务是找出这个社交圈里所有的“社牛”，并按字典序升序输出他们的名字。

解题思路

这是一个图论问题，我们可以将成员看作图的节点，朋友关系看作无向边。问题的核心是计算每个节点的两个关键指标：度（社牛指数）和邻居节点的平均度（朋友平均社牛指数）。

由于成员的名字是字符串，直接用字符串作为图的节点索引不方便，因此我们需要先将每个字符串名字映射到一个唯一的整数 ID。

整个解题过程可以分为三个步骤：

  1. 构建图并计算度数：

    • 我们需要两个映射关系：一个 map 从 string 名字到 int ID，一个 vector 或 array 从 int ID 回到 string 名字。
    • 遍历输入的 对朋友关系，为每个出现的新名字分配一个唯一的整数 ID。
    • 同时，构建图的邻接表表示，并计算每个节点（成员）的度数，即其“社牛指数”。

  2. 计算朋友平均社牛指数：

    • 对于每个成员 ，我们需要计算其所有朋友的社牛指数之和。
    • 遍历成员 的邻接表（即其所有朋友 ），累加这些朋友 的度数 deg(y)，得到总和 sum_deg_y。
    • 成员 的“朋友平均社牛指数”就是 avg(x) = sum_deg_y / deg(x)。

  3. 筛选、排序并输出：

    • 对于每个成员 ，我们比较 deg(x) 和 avg(x)。
    • 为了避免使用浮点数，我们可以将比较条件 deg(x) > sum_deg_y / deg(x) 转换为 deg(x) * deg(x) > sum_deg_y。这个转换不仅避免了精度问题，还自然地处理了 deg(x) = 0 的情况（此时不等式为 0 > 0，不成立）。
    • 将所有满足条件的成员的名字存入一个列表。
    • 最后，对这个列表进行字典序排序。如果列表为空，输出 "None"；否则，按格式输出排序后的名字。

这个算法需要两次遍历图的结构：一次是建立图并计算度数，第二次是基于度数计算邻居的平均度。

代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    map<string, int> name_to_id;
    vector<string> id_to_name;
    vector<vector<int>> adj;
    int next_id = 0;

    auto get_id = [&](const string& name) {
        if (name_to_id.find(name) == name_to_id.end()) {
            name_to_id[name] = next_id++;
            id_to_name.push_back(name);
            adj.emplace_back();
        }
        return name_to_id[name];
    };

    for (int i = 0; i < m; ++i) {
        string u_name, v_name;
        cin >> u_name >> v_name;
        int u = get_id(u_name);
        int v = get_id(v_name);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    int member_count = id_to_name.size();
    if (member_count == 0) {
        cout << "None" << endl;
        return 0;
    }

    vector<long long> deg(member_count);
    for(int i = 0; i < member_count; ++i) {
        deg[i] = adj[i].size();
    }

    vector<string> social_bulls;
    for (int i = 0; i < member_count; ++i) {
        if (deg[i] == 0) continue;

        long long sum_of_friend_degrees = 0;
        for (int neighbor : adj[i]) {
            sum_of_friend_degrees += deg[neighbor];
        }

        if (deg[i] * deg[i] > sum_of_friend_degrees) {
            social_bulls.push_back(id_to_name[i]);
        }
    }

    if (social_bulls.empty()) {
        cout << "None" << endl;
    } else {
        sort(social_bulls.begin(), social_bulls.end());
        for (size_t i = 0; i < social_bulls.size(); ++i) {
            cout << social_bulls[i] << (i == social_bulls.size() - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Map<String, Integer> nameToId = new HashMap<>();
        List<String> idToName = new ArrayList<>();
        List<List<Integer>> adj = new ArrayList<>();
        int nextId = 0;

        for (int i = 0; i < m; i++) {
            String uName = sc.next();
            String vName = sc.next();

            if (!nameToId.containsKey(uName)) {
                nameToId.put(uName, nextId++);
                idToName.add(uName);
                adj.add(new ArrayList<>());
            }
            if (!nameToId.containsKey(vName)) {
                nameToId.put(vName, nextId++);
                idToName.add(vName);
                adj.add(new ArrayList<>());
            }

            int u = nameToId.get(uName);
            int v = nameToId.get(vName);
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        int memberCount = idToName.size();
        if (memberCount == 0) {
            System.out.println("None");
            return;
        }

        long[] deg = new long[memberCount];
        for (int i = 0; i < memberCount; i++) {
            deg[i] = adj.get(i).size();
        }

        List<String> socialBulls = new ArrayList<>();
        for (int i = 0; i < memberCount; i++) {
            if (deg[i] == 0) continue;

            long sumOfFriendDegrees = 0;
            for (int neighbor : adj.get(i)) {
                sumOfFriendDegrees += deg[neighbor];
            }

            if (deg[i] * deg[i] > sumOfFriendDegrees) {
                socialBulls.add(idToName.get(i));
            }
        }

        if (socialBulls.isEmpty()) {
            System.out.println("None");
        } else {
            Collections.sort(socialBulls);
            System.out.println(String.join(" ", socialBulls));
        }
    }
}

import sys

def main():
    try:
        n_str, m_str = sys.stdin.readline().split()
        n, m = int(n_str), int(m_str)
    except (IOError, ValueError):
        print("None")
        return

    name_to_id = {}
    id_to_name = []
    adj = []
    next_id = 0

    def get_id(name):
        nonlocal next_id
        if name not in name_to_id:
            name_to_id[name] = next_id
            id_to_name.append(name)
            adj.append([])
            next_id += 1
        return name_to_id[name]

    for _ in range(m):
        u_name, v_name = sys.stdin.readline().split()
        u = get_id(u_name)
        v = get_id(v_name)
        adj[u].append(v)
        adj[v].append(u)
    
    member_count = len(id_to_name)
    if member_count == 0:
        print("None")
        return
        
    deg = [len(neighbors) for neighbors in adj]

    social_bulls = []
    for i in range(member_count):
        if deg[i] == 0:
            continue
        
        sum_of_friend_degrees = sum(deg[neighbor] for neighbor in adj[i])
        
        if deg[i] * deg[i] > sum_of_friend_degrees:
            social_bulls.append(id_to_name[i])

    if not social_bulls:
        print("None")
    else:
        social_bulls.sort()
        print(" ".join(social_bulls))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：图的构建、度数计算与遍历。核心是通过字符串到整数的映射来高效处理图结构。
  • 时间复杂度：，其中 是成员数， 是关系数。
    • 来自于构建图时对 map 的操作（log N 是 map 查找和插入的复杂度，最多有 次操作，最坏情况下成员数和 相关）。
    • 来自于后续的两次遍历（一次计算度数，一次计算平均度），这部分等价于遍历图的所有节点和边。
  • 空间复杂度：，用于存储图的邻接表、名字与ID的映射关系以及度数数组。