题面解释:

给定一个社交网络拓扑图，其中用户之间通过无向边连接。输入包含三个参数：N表示社交网络中的连接总数，M是需要计算影响力的用户编号，K是跳数范围。接下来有N行，每行两个整数，表示两个用户之间存在直接的社交连接。目标是计算用户M在K跳内能够接触到的不同用户的数量，称为该用户的影响力。输出结果为用户M在指定跳数范围内能够接触到的用户总数。

bfs

计算给定社交网络中某个用户在k跳范围内的影响力，也就是要找到所有距离m,k以内的能访问到的点，最短路问题，数据只有1e3跑一遍bfs(n^2)，之后，枚举所有点，距离小于等于k的ans+=1，最后输出ans-1(除去本身)即可

题解

该问题是典型的图论中的最短路问题，目标是在给定的社交网络中，找到某个用户$M$在$K$跳以内能够接触到的所有用户的数量。由于每条边的权值均为1，因此可以使用广度优先搜索（BFS）来计算从起始用户$M$到其他所有用户的最短路径，然后统计所有距离在$K$以内的用户数量，最终得出用户的影响力。

具体步骤：

1. 构建图结构：使用邻接表存储社交网络中的用户连接关系，每个节点（用户）都可能有多个直接相连的其他节点。

2. BFS计算最短路径：从指定的用户$M$出发，利用BFS来计算其到其他所有用户的最短路径。由于BFS的特点，它能够有效计算无向图中所有节点之间的最短路径。

3. 统计影响力：遍历所有用户，统计与用户$M$之间的最短路径小于等于$K$的用户数量。需要注意的是，影响力不包含用户自身，因此最终结果需要减去1。

复杂度分析：

• 时间复杂度：由于图的节点数量最多为1000，且BFS的时间复杂度为$O(N + E)$，即节点和边数之和，因此对于最多$N = 1000$的场景，可以在合理时间内完成运算。
• 空间复杂度：邻接表存储节点和边的信息，BFS过程中还需要一个队列和距离数组，空间复杂度为$O(N + E)$，也是可以接受的。

代码说明：

1. 输入处理：首先读取网络中的连接关系，将每个连接存储在邻接表中。
2. BFS部分：使用队列实现BFS算法，从指定的用户$m$开始搜索。对于每一个节点，如果找到一个新的更短的路径，则更新该节点的距离，并继续搜索。
3. 结果计算：遍历所有节点，统计距离小于等于$K$的节点数量，最后输出时减去1，排除用户自身。

代码如下

cpp

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

#define N 200005  // 定义最大节点数，预留足够大空间
int dis[N];       // 用来存储每个节点到起点的最短距离
int n, m, k;      // n表示社交网络中的边数，m表示需要计算的用户编号，k表示跳数范围
int inf = INT_MAX; // 定义一个无穷大值，表示节点还未访问
vector<int> g[N];  // 使用邻接表来表示图，g[i]表示与节点i直接相连的节点

// BFS函数，用于从起始点s开始计算所有节点的最短距离
void bfs(int s) {
	queue<int> q; // 创建一个队列用于BFS
	// 初始化所有节点的距离为无穷大，表示还未被访问
	for (int i = 0; i <= 1000; i++) dis[i] = inf;
	dis[s] = 0;  // 起始节点到自己的距离为0
	q.push(s);   // 将起始节点加入队列

	// 开始BFS
	while (!q.empty()) {
		int u = q.front(); // 取出队列前端节点
		q.pop();
		// 遍历与当前节点相连的所有节点
		for (int v : g[u]) {
			// 如果从当前节点到相邻节点的距离小于当前已知最短距离，则更新
			if (dis[v] > dis[u] + 1) {  // BFS每条边的权值都为1
				dis[v] = dis[u] + 1;    // 更新最短距离
				q.push(v);              // 将相邻节点加入队列进行进一步的搜索
			}
		}
	}
}

signed main() {
	cin >> n >> m >> k; // 输入边数n、需要计算的用户编号m、跳数范围k
	// 输入社交网络中的连接关系，并将其存入邻接表
	for (int i = 1; i <= n; i++) {
		int u, v;
		cin >> u >> v;
		// 因为是无向图，所以需要双向存储
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	bfs(m); // 从用户m开始进行BFS，计算最短距离

	int ans = -1; // 初始值为-1，表示最后不计算用户自身
	// 遍历所有节点，统计在k跳以内的节点数量
	for (int i = 0; i <= 1000; i++) {
		ans += (dis[i] <= k); // 如果节点i到用户m的最短距离不大于k，则计入影响力
	}
	cout << ans << '\n'; // 输出最终结果
	return 0;
}

python

from collections import deque

N = 200005
inf = float('inf')
dis = [inf] * N
g = [[] for _ in range(N)]

def bfs(s):
    for i in range(1001):
        dis[i] = inf  # 初始化所有节点的距离为无穷大
    dis[s] = 0  # 起点的距离设为0
    q = deque([s])  # 队列初始化，将起点入队
    while q:
        u = q.popleft()  # 取出队列中的第一个元素
        for v in g[u]:  # 遍历当前节点的邻居
            if dis[v] > dis[u] + 1:  # 如果经过当前节点能使邻居距离更短
                dis[v] = dis[u] + 1  # 更新邻居的最短距离
                q.append(v)  # 将邻居节点加入队列

n, m, k = map(int, input().split())  # 读取n、m和k
for _ in range(n):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

bfs(m)  # 从节点 m 开始 BFS
ans = -1
for i in range(1001):
    ans += (dis[i] <= k)  # 统计距离小于等于 k 的节点个数

print(ans)

java

import java.util.*;

public class Main {
    static int N = 200005;
    static int inf = Integer.MAX_VALUE;
    static int[] dis = new int[N];  // 距离数组
    static List<List<Integer>> g = new ArrayList<>(N);  // 图的邻接表

    static void bfs(int s) {
        for (int i = 0; i <= 1000; i++) {
            dis[i] = inf;  // 初始化距离数组，所有节点距离为无穷大
        }
        dis[s] = 0;  // 起点的距离设为0
        Queue<Integer> q = new LinkedList<>();  // 队列初始化
        q.add(s);  // 将起点加入队列
        while (!q.isEmpty()) {
            int u = q.poll();  // 从队列中取出一个节点
            for (int v : g.get(u)) {  // 遍历邻居节点
                if (dis[v] > dis[u] + 1) {  // 如果能通过当前节点缩短邻居的距离
                    dis[v] = dis[u] + 1;  // 更新邻居的最短距离
                    q.add(v);  // 将邻居节点加入队列
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        for (int i = 0; i < N; i++) g.add(new ArrayList<>());  // 初始化图的邻接表

        for (int i = 0; i < n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            g.get(u).add(v);
            g.get(v).add(u);
        }

        bfs(m);  // 从节点 m 开始 BFS
        int ans = -1;
        for (int i = 0; i <= 1000; i++) {
            if (dis[i] <= k) ans++;  // 统计距离小于等于 k 的节点个数
        }

        System.out.println(ans);
    }
}

题目内容

社交网络拓扑图中的节点表示社交网络中的用户，边表示两个用户之间的社交连接，边是无向的，两个用户最多只有一条直接相连的边。用户的影响力定义为：从某个社交网络用户开始，找出所有可以在$K$跳(直接或间接关系)内接触到的其他用户的总个数。

请实现一个程序，计算给定社交网络中某个用户在$k$跳范围内的影响力。

输入描述

• 第一行输入$N\ M\ K$(三个空格分隔的正整数)：$N$代表社交网络连接总数，$M$代表需要计算影响力的用户编号，$K$代表计算影响力的范围。$1≤N,K≤1000,0≤M<1000$
• 接下来的$N$行，每行两个整数$X\ Y(0≤X,Y≤1000)$，代表社交网络中一条直接连接的边，如"$1\ 2$"代表$1$号与$2$号用户互相直接连接。
• 用例确保输入有效，无需进行校验

输出描述

输出$M$用户在$K$跳范围内的影响力

样例1

输入

5 0 2 
0 1
1 2
2 3
3 4
4 0

输出

4

样例2

输入

8 0 3
0 1
0 2
0 3
3 4
2 5
5 4
2 3
1 5

输出

5