思路：BFS/DFS/并查集

题目要求从1号节点出发，k步之内能够到达哪些节点。这是一个典型的图遍历问题，我们可以使用广度优先搜索（BFS）来解决。

首先，我们需要创建一个队列，将1号节点放入队列，并将其标记为已访问。

然后，我们开始进行BFS。在每一轮中，我们首先获取当前队列的大小，这个大小就是当前步数可以到达的节点数量。然后，我们遍历这些节点，对于每一个节点，我们将其所有未访问过的邻居节点放入队列，并将这些邻居节点标记为已访问。在这个过程中，我们需要记录当前的步数，如果步数达到$k$，我们就停止遍历。

最后，我们输出所有被标记为已访问的节点，这些节点就是从1号节点出发，$k$步之内能够到达的所有节点

本题也可以使用DFS或并查集求解，感兴趣的小伙伴可以自行尝试一下

代码

C++

#include<bits/stdc++.h>
using namespace std;
const int N=1E5+10;
vector<int>g[N];
long long n,k,w[N];
bool st[N];
void bfs(){
    st[1]=true;
    queue<int>q;
    q.push(1);
    long long depth=0;
    while(q.size()){
        int sz=q.size();
        depth++;
        for(int i=0;i<sz;i++){
            int t=q.front();
            q.pop();
            for(int &x:g[t]){
                if(!st[x]&&depth<k){
                    st[x]=true;
                    q.push(x);
                }
            }
        }
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=n;i++){
        g[i].push_back(w[i]);
    }
    bfs();
    for(int i=1;i<=n;i++){
        if(st[i]){
            cout<<i<<" ";
        }
    }
    return 0;
}

Java

import java.util.*;

public class Main {
    static ArrayList<Integer> ans;
    static boolean[] vis;
    static LinkedList<Integer>[] g;
    static long k;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        k = in.nextLong();
        g = new LinkedList[n + 1];
        vis = new boolean[n + 1];
        ans = new ArrayList();
        Arrays.setAll(g, e -> new LinkedList());
        for (int i = 1; i <= n; i++) {
            int u = in.nextInt();
            g[i].add(u);
        }
        dfs(1, k);
        Collections.sort(ans);
        for (Integer num : ans) {
            System.out.print(num + " ");
        }

    }
    public static void dfs(int cur, long k) {
        if (vis[cur]) return;
        if (k < 0) return;
        ans.add(cur);
        vis[cur] = true;
        for (Integer son : g[cur]) {
            dfs(son, k - 1);
        }
    }
}

Python

while True:
    try:
        n, k = map(int, input().split())
        edges = list(map(int, input().split()))

        visited = [1]
        i = 0
        while i<=k and edges[visited[-1]-1] not in visited:
            visited.append(edges[visited[-1]-1])
            i += 1
        
        for j in sorted(visited):
            print(j, end=' ')

    except EOFError:
        break

题目描述

给定一个有向图，一共有$n$个节点以及$n$条边，问：从1号节点出发，$k$步之内能够到达哪些节点？

输入描述

第一行两个整数$n,k$，表示节点的数量，以及最多走的步数

第二行$n$个整数$a_i$，表示从$i$到$a_i$有一条有向边

1$\leq n \leq 10^5$

$1 \leq k \leq 10^{18}$

$1 \leq a_i \leq n$

输出描述

能到达的节点的编号，按从小到大的顺序输出。

样例

输入

5 100
5 4 5 2 3

输出

1 3 5