2 solutions

  • 0
    @ 2024-9-5 0:47:48 
    from collections import Counter
n,m,k,l = map(int,input().split())
nmap = [[0]*n for _ in range(n)]

for _ in range(m):
    x,y = map(int,input().split())
    nmap[x-1][y-1] = 1
    nmap[y-1][x-1] = 1

infos = Counter()
def dfs(ids,path:list):
    if len(path)>=2:
        if path[1]!=k-1:
            infos.update([path[1]])
        return

    for i in range(n):
        if nmap[ids][i]==1:
            path.append(i)
            dfs(i,path)
            path.pop()

dfs(k-1,[])
for i in range(n):
    if nmap[k-1][i]:
        if i in infos:
            del infos[i]
    else:
        if i not in infos:
            infos[i] = 0
del infos[k-1]
results= list(infos.items())
results.sort(key=lambda x:( -x[1],x[0]))
results = [each[0]+1 for each in results]
results = results[:l]
if len(results)<l:
    results = results + [0]*(l-len(results))
print(" ".join(map(str,results)))
    • 0
      @ 2024-9-4 19:57:54

      题面描述:

      在这个问题中，我们需要为社交网络平台上的用户提供好友推荐功能。具体而言，输入包括用户总数 (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;
}
      • 1

      2024.9.4-秋招-第2题-好友推荐系统

      Information

      ID
      108
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      5
      Tags
      # Submissions
      672
      Accepted
      192
      Uploaded By
      1. About
      2. Contact Us
      3. Privacy
      4. Terms of Service
      5. Copyright Complaint
      6. Language
      7. Legacy mode
      8. Theme
      2. 湘ICP备2023007293号
      3. Worker 0, 28ms
      4. Powered by Hydro v4.14.1 Community