题解 | #我朋友的朋友不是我的朋友#

题目链接

题目描述

共有 $n$ 位成员，给出 $m$ 对互为好友的关系（无向边）。记成员 $x$ 的社牛指数为其好友数 $\deg(x)$ ；朋友平均社牛指数为 $\operatorname{avg}(x)=\dfrac{1}{\deg(x)}\sum\limits_{y\in N(x)}\deg(y)$ 。若 $\deg(x) > \operatorname{avg}(x)$ ，则称 $x$ 为社牛。请按字典序输出所有社牛成员的姓名；若不存在，输出 None。

输入：

第一行两个整数 $n$ 、 $m$
接下来 $m$ 行，每行两个字符串 $u$ 、 $v$ 表示 $u$ 与 $v$ 互为好友

输出：

一行若干个字符串，按字典序升序输出所有社牛；若不存在仅输出 None

解题思路

将姓名离散化为编号，建无向图。
先统计每个成员的度数 $\deg(\cdot)$ ；再对每个成员求其邻居度数之和 $S(x)=\sum\deg(y)$ 。
判断条件等价于 $\deg(x)>\operatorname{avg}(x)\iff S(x) < \deg(x)\cdot\deg(x)$ （当 $\deg(x)=0$ 时无朋友，视为非社牛）。
将满足条件的姓名收集并按字典序排序输出。
复杂度：建图与求和 $\mathcal{O}(n+m)$ ，排序输出 $\mathcal{O}(k\log k)$ 。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    unordered_map<string, int> id;
    vector<pair<string,string>> edges;
    edges.reserve(m);
    int idx = 0;
    for (int i = 0; i < m; ++i) {
        string u, v; cin >> u >> v;
        edges.emplace_back(u, v);
        if (!id.count(u)) id[u] = idx++;
        if (!id.count(v)) id[v] = idx++;
    }
    int N = idx;
    vector<vector<int>> g(N);
    vector<int> deg(N, 0);
    vector<string> names(N);
    for (auto &kv : id) names[kv.second] = kv.first;
    for (auto &e : edges) {
        int u = id[e.first], v = id[e.second];
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++; deg[v]++;
    }
    vector<long long> sumNei(N, 0);
    for (int u = 0; u < N; ++u) {
        long long s = 0;
        for (int v : g[u]) s += deg[v];
        sumNei[u] = s;
    }
    vector<string> ans;
    for (int u = 0; u < N; ++u) {
        if (deg[u] > 0 && sumNei[u] < 1LL * deg[u] * deg[u]) ans.push_back(names[u]);
    }
    sort(ans.begin(), ans.end());
    if (ans.empty()) {
        cout << "None\n";
    } else {
        for (int i = 0; i < (int)ans.size(); ++i) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

import java.util.*;

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> id = new HashMap<>();
        List<String> U = new ArrayList<>(), V = new ArrayList<>();
        int idx = 0;
        for (int i = 0; i < m; i++) {
            String u = sc.next();
            String v = sc.next();
            U.add(u); V.add(v);
            if (!id.containsKey(u)) id.put(u, idx++);
            if (!id.containsKey(v)) id.put(v, idx++);
        }
        int N = idx;
        List<Integer>[] g = new ArrayList[N];
        for (int i = 0; i < N; i++) g[i] = new ArrayList<>();
        int[] deg = new int[N];
        String[] name = new String[N];
        for (Map.Entry<String,Integer> e : id.entrySet()) name[e.getValue()] = e.getKey();
        for (int i = 0; i < m; i++) {
            int u = id.get(U.get(i));
            int v = id.get(V.get(i));
            g[u].add(v); g[v].add(u);
            deg[u]++; deg[v]++;
        }
        long[] sumNei = new long[N];
        for (int u = 0; u < N; u++) {
            long s = 0;
            for (int v : g[u]) s += deg[v];
            sumNei[u] = s;
        }
        List<String> ans = new ArrayList<>();
        for (int u = 0; u < N; u++) {
            if (deg[u] > 0 && sumNei[u] < 1L * deg[u] * deg[u]) ans.add(name[u]);
        }
        if (ans.isEmpty()) {
            System.out.println("None");
        } else {
            Collections.sort(ans);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < ans.size(); i++) {
                if (i > 0) sb.append(' ');
                sb.append(ans.get(i));
            }
            System.out.println(sb.toString());
        }
    }
}

n, m = map(int, input().split())
U, V = [], []
id_map = {}
idx = 0
for _ in range(m):
    u, v = input().split()
    U.append(u); V.append(v)
    if u not in id_map:
        id_map[u] = idx; idx += 1
    if v not in id_map:
        id_map[v] = idx; idx += 1
N = idx
g = [[] for _ in range(N)]
deg = [0] * N
names = [None] * N
for name, i in id_map.items():
    names[i] = name
for i in range(m):
    u = id_map[U[i]]; v = id_map[V[i]]
    g[u].append(v); g[v].append(u)
    deg[u] += 1; deg[v] += 1
sum_nei = [0] * N
for u in range(N):
    s = 0
    for v in g[u]:
        s += deg[v]
    sum_nei[u] = s
ans = [names[u] for u in range(N) if deg[u] > 0 and sum_nei[u] < deg[u] * deg[u]]
if not ans:
    print('None')
else:
    ans.sort()
    print(' '.join(ans))

算法及复杂度

算法：建图、度数统计、邻居度数求和，判定 $S(x) > \deg(x)\cdot\deg(x)$ 收集并排序姓名
时间复杂度： $\mathcal{O}(n+m)$
空间复杂度： $\mathcal{O}(n+m)$