题面描述:

在这个问题中，我们需要为社交网络平台上的用户提供好友推荐功能。具体而言，输入包括用户总数 (N)、好友关系总数 (M)、待推荐用户编号 (K) 以及需要推荐的好友数量 (L)。随后会有 (M) 行数据，表示用户之间的好友关系。我们需根据用户 (K) 的共同好友数量来计算其与其他用户的相似度，推荐相似度最高的 (L) 个用户，且推荐用户不能是用户 (K) 的好友。推荐结果需按相似度从高到低排序，若相似度相同，则按用户编号从小到大排序。如果找到的候选用户少于 (L) 个，则需要补充与用户 (K) 没有任何共同好友的其他用户，如果仍不足 (L) 个，则用 (0) 补位。通过这个推荐功能，可以帮助用户发现新的好友，增强社交网络的互动。

思路：模拟

题目要求给目标用户推荐好友，首先被推荐对象不能是目标用户的好友。因此我们在读入用户关系时，标记一下与目标用户互为好友的用户。

之后，枚举所有未被标记用户，他们都是待定对象。而与目标用户相似度，就是与其相连的边中，被标记的点的数量。因此统计后再排序即可。

具体步骤如下：

1. 数据结构定义：

   • 使用一个大小为 maxn 的数组 vis 来标记特定用户 (g) 的好友。若用户 (i) 是 (g) 的好友，则 vis[i] 为 true。
   • 使用邻接表 e 来存储每个用户的好友列表，以便后续快速查找每个用户的好友。

2. 读取输入：

   • 首先读取用户总数 (n)、好友关系数 (m)、特定用户编号 (g)、以及要输出的推荐好友数量 (p)。
   • 接下来，逐条读取好友关系 (x) 和 (y)，并更新邻接表和 vis 数组。若 (x) 或 (y) 是用户 (g)，则将其标记为与 (g) 直接相连。

3. 计算相似度：

   • 遍历所有用户 (i)，跳过已标记为与 (g) 相连的用户。
   • 对于每个未被标记的用户 (i)，计算其与 (g) 的相似度，即其好友中有多少是与 (g) 直接相连的用户。通过一个辅助数组 show 来避免重复计数。

4. 记录和排序：

   • 将每个用户及其相似度（得分）存储在结构体数组 b 中。记录符合条件的用户数量 cnt。
   • 对 b 数组进行排序，首先根据得分从高到低，其次根据用户编号从小到大进行排序。这保证了我们能够优先推荐相似度高的用户。

5. 输出结果：

   • 最后输出前 (p) 个得分最高的用户编号。如果得分用户少于 (p) 个，程序可以调整输出，以确保数量符合要求（此题未涉及，代码中未处理，但可根据需求调整）。

代码

java

import java.util.*;

public class Main {

    static final int MAXN = 100010; // 定义最大节点数量为 100010
    static int n, m, g, p; // n: 节点数, m: 边数, g: 特定节点, p: 要输出的节点数
    static boolean[] vis = new boolean[MAXN]; // 记录特定节点 g 相连的节点
    static List<Integer>[] e = new ArrayList[MAXN]; // 邻接表，用于存储图中的边
    static int cnt; // 记录符合条件的节点数量
    static boolean[] show = new boolean[MAXN]; // 辅助数组，用于记录某个节点的邻居是否已被访问过

    static class Node {
        int id, score; // 节点编号和得分
        Node(int id, int score) {
            this.id = id;
            this.score = score;
        }
    }

    static Node[] b = new Node[MAXN]; // 存储每个符合条件节点的编号和得分

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); // 读取节点数
        m = scanner.nextInt(); // 读取边数
        g = scanner.nextInt(); // 读取特定节点 g
        p = scanner.nextInt(); // 读取要输出的节点数

        for (int i = 0; i < MAXN; i++) {
            e[i] = new ArrayList<>(); // 初始化邻接表
        }

        for (int i = 1; i <= m; ++i) {
            int x = scanner.nextInt(); // 读取每条边的第一个节点 x
            int y = scanner.nextInt(); // 读取每条边的第二个节点 y
            e[x].add(y); // 将 y 加入到 x 的邻接表中
            e[y].add(x); // 将 x 加入到 y 的邻接表中
            if (x == g || y == g) { // 如果 x 或 y 中有一个是特定节点 g
                vis[x] = true; // 标记 x 为与 g 相连
                vis[y] = true; // 标记 y 为与 g 相连
            }
        }

        for (int i = 1; i <= n; ++i) {
            if (vis[i]) continue; // 如果节点 i 与 g 相连，跳过
            int score = 0; // 初始化得分为 0
            Arrays.fill(show, false); // 重置 show 数组

            for (int x : e[i]) { // 遍历节点 i 的所有邻居
                if (vis[x] && !show[x]) { // 如果邻居 x 与 g 相连且未被访问过
                    score += 1; // 增加得分
                    show[x] = true; // 标记邻居 x 已被访问
                }
            }
            b[++cnt] = new Node(i, score); // 将节点 i 和其得分记录下来
        }

        Arrays.sort(b, 1, cnt + 1, (x, y) -> {
            // 根据得分排序，如果得分相同，按节点编号升序排序
            if (x.score == y.score) return Integer.compare(x.id, y.id);
            return Integer.compare(y.score, x.score);
        });

        int outputCount = Math.min(p, cnt); // 计算实际可输出的节点数

        for (int i = 1; i <= outputCount; ++i) {
            System.out.print(b[i].id + " "); // 输出得分最高的节点的编号
        }

        for (int i = outputCount + 1; i <= p; ++i) {
            System.out.print("0 "); // 如果不足 p 个节点，补充 0
        }
    }
}

python

n , m , k , L = map(int, input().split())
edges = [[] for _ in range(n + 1)]

# 读入数据
for _ in range(m):
    x , y = map(int, input().split())
    edges[x].append(y)
    edges[y].append(x)
# 去重排序
for i in range(1 , n + 1):
    edges[i] = list(set(edges[i]))
    edges[i].sort()
# 计算共同好友
def get_commend_friend(x , y):
    i = 0
    ans = 0
    st = set(edges[y])
    for item in edges[x]:
        if item in st:
            ans += 1
    return ans
# 计算答案
res = []
for i in range(1 , n + 1):
    # 排除自己
    if i == k:
        continue
    # 排除已经是好友的
    if k in edges[i]:
        continue
    # 计算共同好友
    res.append([get_commend_friend(k , i) , i])
# 排序输出，注意排序规则：共同好友数目降序，编号升序
res.sort(key = lambda x : (-x[0] , x[1]))
ans = []
# 输出答案
for i in range(L):
    if i < len(res):
        ans.append(res[i][1])
    else:
        ans.append(0)
print(*ans)

C++

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

const int maxn = 1e5 + 10; // 定义最大节点数量为 100010
int n, m, g, p; // n: 节点数, m: 边数, g: 特定节点, p: 要输出的节点数
int vis[maxn]; // 记录特定节点 g 相连的节点
vector<int> e[maxn]; // 邻接表，用于存储图中的边

int cnt; // 记录符合条件的节点数量
bool show[maxn]; // 辅助数组，用于记录某个节点的邻居是否已被访问过
struct node {
	int id, score; // 节点编号和得分
} b[maxn]; // 存储每个符合条件节点的编号和得分

int main() {
    std::ios::sync_with_stdio(false); // 提高 cin/cout 的运行效率
    cin >> n >> m >> g >> p; // 读取输入的 n, m, g, p 的值
    int x, y;
    for (int i = 1; i <= m; ++i) {
    	cin >> x >> y; // 读取每条边的两个节点 x 和 y
    	e[x].push_back(y); // 将 y 加入到 x 的邻接表中
    	e[y].push_back(x); // 将 x 加入到 y 的邻接表中
    	if (x == g || y == g) { // 如果 x 或 y 中有一个是特定节点 g
    		vis[x] = true; // 标记 x 为与 g 相连
    		vis[y] = true; // 标记 y 为与 g 相连
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) continue; // 如果节点 i 与 g 相连，跳过
		int score = 0; // 初始化得分为 0
		memset(show, 0, sizeof show); // 重置 show 数组
		for (auto x : e[i]) { // 遍历节点 i 的所有邻居
			if (vis[x] && !show[x]) { // 如果邻居 x 与 g 相连且未被访问过
				score += 1; // 增加得分
				show[x] = true; // 标记邻居 x 已被访问
			}
		}
		b[++cnt] = (node){i, score}; // 将节点 i 和其得分记录下来
	}
	sort(b + 1, b + cnt + 1, [&](node x, node y) {
		// 根据得分排序，如果得分相同，按节点编号升序排序
		return x.score == y.score ? x.id < y.id : x.score > y.score;	
	});
	for (int i = 1; i <= p; ++i) {
		cout << b[i].id << " "; // 输出得分最高的 p 个节点的编号
	}
    
    return 0;
}

题目内容

你正在为一个社交网络平台开发好友推荐功能。

平台上有$N$个用户(每个用户使用$1$到$N$的整数编号)，同时系统中维护了用户之间的好友关系。

为了推荐新朋友，平台决定采用“共同好友数量”作为衡量两个用户之间相似度的标准。

系统根据输入用户编号$K$，输出与此用户$K$相似度最高的前$L$个用户$ID$，来推荐给用户$K$。

相似度定义:两个用户非好友，两个用户的相似度为拥有的共同好友数(例如用户$A$和用户$B$，只有共同好友$C$和$D$，相似度=$2$)

输入描述

第一行包含四个整数$N$，$M$、$K$和$L$，分别表示用户的数量($N$)，好友记录条数($M$)、查询的用户编号($K$)和推荐的好友数量($L$)。

接下来$M$行，每行包含两个整数编号$X$和$Y$，表示编号为$X$和$Y$用户是好友。

1.输入格式都是标准的，无需考虑输出异常场景(不会包含用户和自己是好友的输入,例如$1$ $1$)

2.用户数不超过$1024$，用户编码最大$10244$

3.好友记录数不超过$10240$

输出描述

根据输入$K$和$L$，输出和用户$K$相似度最高的$L$个用户编码。

1.输出相似度最高的前$L$个用户编码，按照相似度从高到低排序

2.如果有相似度相同的可能好友，按照用户编号从小到大排序

3.如果推荐的好友个数不足$L$个，则推荐与用户$K$无无共同好友关系的用户(陌生人)作为可能好友;如果 推荐仍不满足$L$个用户，剩余推荐用户编码使用$0$来占位

样例1

输入

6 7 3 2
1 2
1 3
2 3
3 4
3 5
4 5
5 6

输出

6 0

解释

输入包含了$6$个用户，$7$条好友记录，给用户$ID$编号为$3$的用户推荐$2$个好友

输出只有编号为$6$的用户可能是编号$3$用户的可能好友；

尝试推荐与编号$3$用户无共同好友的其他用户，由于除编号为$6$的用户之外，其他用户和编号$3$用户都是好友，所以找不到陌生人作为推荐的第二个用户；

推荐结果不足$2$个用户，所以推荐的第二个用户编码使用$0$来占位补足。

样例2

输入

8 11 1 3
1 2
1 3
2 3
3 4
3 5
4 5
5 6
6 7
7 8
1 8
2 7

输出

7 4 5

解释

输入包含了$8$个用户，$11$条好友记录，给用户$ID$编号为$1$的用户推荐$3$个好友。

按照相似度排序推荐给用户$1$的相关好友:$7$ $4$ $5$