利用哈希表中map记录邻接关系，set记录影响的用户，逐层的获得被影响的用户，并输出set的大小。

#include<iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
using namespace std;

int main(){
    int n,m,k;
    cin>>n>>m>>k;

    // map记录邻接关系
    unordered_map<int,vector<int>> map;
    // set记录在指定范围内的用户数目
    unordered_set<int> set;

    for (int i = 0; i < n; i++) {
        int a,b;
        cin>>a>>b;
        map[a].push_back(b);
        map[b].push_back(a);
    }

    vector<int> res;
    queue<int> que;
    que.push(m);
    int count = 0;
    while(!que.empty()){
        // 逐步的对 1  2 .. k 步影响力的节点加入set
        int size = que.size();
        for (int i = 0; i < size;i++) {
            int tmp = que.front();
            que.pop();
            res = map[tmp];
            for (int j = 0; j < res.size(); j++) {
                // 已经在set中避免重复加入que，否则导致超时
                if (set.find(res[j]) == set.end()) {
                        que.push(res[j]);
                }
                // 排除自身
                if (res[j] != m){  
                    set.insert(res[j]);
                }  
            }
        }
        count++;
        // 达到k步后跳出循环
        if (count == k) {
            break;
        }   
    }

    // set的数量即为可以影响的用户数目
    cout<<set.size()<<endl;
    return 0;
}

from collections import deque
N = 1005
inf = float('inf')
dis = [inf]*N
g = [[] for _ in range(N)]

def bfs(s):
    for i in range(N):
        dis[i]=inf
    dis[s]=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())
for i in range(n):
    u,v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

bfs(m)
ans = -1
for i in range(N):
    if dis[i]<=k:
        ans+=1
print(ans)

# DFS & set

from collections import defaultdict

n, m, k = map(int, input().split())

ls = []
for _ in range(n):
    ls.append(list(map(int, input().split())))

dc = defaultdict(set)

for a, b in ls:
    dc[a].add(b)
    dc[b].add(a)


def dfs(graph, start, influence):
    stack = [(start, influence)]
    vis = [start]
    count = 0

    while stack:
        node, influence = stack.pop()
        
        for neighbor in dc[node]:
            if neighbor not in vis and influence > -1:
                count += 1
                vis.append(neighbor)
                stack.append((neighbor, influence - 1))

    return count

print(dfs(dc, m, k))

from collections import deque

n, m, k = map(int, input().split())
net = [[0] * n for _ in range(n)]
for i in range(n):
    id1, id2 = map(int, input().split())
    net[id1][id2] = net[id2][id1] = 1
res = 1
users = set()
users.add(m)
q = deque()
for i in range(n):
    if net[m][i] == 1:
        q.append(i)

for i in range(k):
    num = len(q)
    for j in range(num):
        tmp = q.popleft()
        if tmp not in users:
            res += 1
            users.add(tmp)
            for l in range(n):
                if net[tmp][l] == 1:
                    q.append(l)

print(res - 1)

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

int main() {
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<int>> g(n);
    for (int i=0; i<n; i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
   
    vector<bool> vis(n,false);
    vector<int> dep(n,INT_MAX);

    vis[m]=true;
    queue<int> q;
    q.push(m);
    dep[m]=0;

    while (!q.empty()) {
        int cur=q.front();
        q.pop();
        for (auto a:g[cur]) {
            if (!vis[a]) {
             q.push(a);
             dep[a]=dep[cur]+1;
             vis[a]=true;
            }
        }
    }

    int res=0;
    for (int i=0; i<n; i++) {
        if (dep[i]<=k) {
            res++;
        }
    }

    cout<<res-1<<endl;
}

Dijkstra

#include<bits/stdc++.h>
using namespace std;
int N,M,K;
vector<vector<int>>mp(1010);
struct STU{
	int x,dist;
	STU(int x,int dist):x(x),dist(dist){}
};
struct comparestu{
	bool operator()(const STU&a,const STU&b){
		return a.dist>b.dist;
	}
};
void Dijkstra(int st){
	const int inf=1e9+7;
	vector<int>dist(1010,inf);
	vector<bool>book(1010,0);
	dist[st]=0; book[st]=1;
	priority_queue<STU,vector<STU>,comparestu>pri;
	pri.push(STU(st,0));
	while(!pri.empty()){
		int x=pri.top().x;
		for(int i=0;i<(int)mp[x].size();i++){
			int y=mp[x][i];
			if(dist[y]>dist[x]+1){
				dist[y]=dist[x]+1;
				if(book[y])continue;
				book[y]=1;
				pri.push(STU(y,dist[y]));
			}
		}
		pri.pop();
	}
	int ans=0;
	for(int i=0;i<=1000;i++)
		if(i!=st&&dist[i]<=K) ans++;
	cout<<ans;
}
int main(){
	cin>>N>>M>>K;
	for(int i=1;i<=N;i++){
		int x,y;
		cin>>x>>y;
		mp[x].push_back(y);
		mp[y].push_back(x);
	}
	Dijkstra(M);
}

题面解释:

给定一个社交网络拓扑图，其中用户之间通过无向边连接。输入包含三个参数：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);
    }
}