1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 和 PrintWriter 提升大规模数据下的 I/O 效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 1. 读取成员数 n 和 好友关系数 m
        String[] strA = br.readLine().trim().split("\\s+");
        int n = Integer.parseInt(strA[0]);
        int m = Integer.parseInt(strA[1]);

        // nameToID: 将字符串姓名映射为整数 ID，方便作为数组下标处理
        HashMap<String, Integer> nameToID = new HashMap<>();
        // idToName: 将整数 ID 映射回姓名，用于最后的结果输出
        String[] idToName = new String[n];
        // adj: 邻接表，存储每个人的好友列表
        List<Integer>[] adj = new ArrayList[n];
        // deg: 存储每个人的“社牛指数”（即节点的度数）
        int[] deg = new int[n];
        int idCount = 0; // 记录当前已分配的 ID 数量

        // 2. 构建图结构
        for (int i = 0; i < m; i++) {
            String[] pair = br.readLine().trim().split("\\s+");

            // 处理每一对好友关系中的两个姓名
            for (String name : pair) {
                // 如果是第一次见到的姓名，分配一个新的 ID 并初始化其邻接表
                if (!nameToID.containsKey(name)) {
                    idToName[idCount] = name;
                    adj[idCount] = new ArrayList<>();
                    nameToID.put(name, idCount++);
                }
            }

            // 获取两个好友对应的 ID
            int u = nameToID.get(pair[0]);
            int v = nameToID.get(pair[1]);

            // 无向图：双方互相添加进对方的好友列表
            adj[u].add(v);
            adj[v].add(u);

            // 双方的度数各加 1
            deg[u]++;
            deg[v]++;
        }

        // 3. 判定“社牛”成员
        List<String> res = new ArrayList<>();
        for (int i = 0; i < idCount; i++) {
            // 孤立点（没有好友的人）不符合社牛定义
            if (deg[i] == 0) {
                continue;
            }

            // sum: 累计该成员所有好友的度数总和
            long sum = 0;
            for (int neighbor : adj[i]) {
                sum += deg[neighbor];
            }

            /**
             * 判定公式推导：
             * 原条件：deg(x) > (sum_of_friends_deg / deg(x))
             * 变形得：deg(x) * deg(x) > sum_of_friends_deg
             *
             * 优点：避免浮点数除法导致的精度丢失。
             * 注意：deg 最大为 10^5，平方后达 10^10，超过了 int 范围，必须强转为 long 计算。
             */
            if ((long) deg[i] * deg[i] > sum) {
                res.add(idToName[i]);
            }
        }

        // 4. 输出处理
        if (res.isEmpty()) {
            // 若不存在任何社牛，输出 None
            out.println("None");
        } else {
            // 题目要求按字典序升序输出
            Collections.sort(res);
            for (int i = 0; i < res.size(); i++) {
                // 格式化输出：姓名之间用单个空格分隔
                out.print(res.get(i) + (i == res.size() - 1 ? "" : " "));
            }
            out.println();
        }

        // 5. 刷新缓冲区并关闭资源
        out.flush();
        out.close();
        br.close();
    }