c++ - 如何以最小距离在树中找到 S 个或更少的节点？

Question

给定一个具有 N 个节点和 N-1 条边的无权无向 n 叉树。节点编号从 0 到 N-1。我需要找到S个或更少的节点，以便以最小距离D到达每个节点。输入的第一行是N（节点数）和S（最大输出节点数）。接下来的 N-1 行是边的描述。在输出时，我必须写出 D、S´（我使用的节点数）和 S´ 中的标记节点。示例：输入：

16 3
3 0
3 11
11 4
0 15
15 13
4 2
0 1
1 8
15 12
3 10
11 14
14 6
2 5
13 9
15 7

输出：

3 2
0
11

其他正确输出：

3 3
5
6
15

我认为我应该使用深度优先搜索并计算距 S 最近节点的距离，并且我应该使用二进制搜索来搜索最小 D。但是我在 c++ 中的实现存在问题。现在我有代码，可以创建树，但我不知道在这种情况下如何使用深度优先搜索。

#include <iostream>
#include <stack>
#include <vector>
#include <stdio.h>
using namespace std;

// data structure to store graph edges
struct Edge {
    int src, dest;
};

// class to represent a graph object
class Graph
{
public:
    // construct a vector of vectors to represent an adjacency list
    vector<vector<int>> adjList;

    // Graph Constructor
    Graph(vector<Edge> const &edges, int N)
    {
        // resize the vector to N elements of type vector<int>
        adjList.resize(N);

        // add edges to the undirected graph
        for (auto &edge: edges)
        {
            adjList[edge.src].push_back(edge.dest);
            adjList[edge.dest].push_back(edge.src);
        }
    }
};

int main()
{
    int N, S;   // Number of nodes in the graph and number of 
    scanf("%d", &N);
    // vector of graph edges as per above diagram
    vector<Edge> edges;
    int a,b;
    for(int i = 0; i < (N-1); i++)
    {
        scanf("%d %d", &a, &b);
        edges.push_back({a, b});
    }
    // create a graph from given edges
    Graph graph(edges, N);

    return 0;
}

标签： c++algorithmtreedepth-first-search