求将所有乘客送至1号公交站所需的最少巴士数量

给定一座城市，包含N个公交站和N-1条道路，所有公交站通过道路互相可达。每个站点的值为0或1，0表示该站点无乘客，1表示有乘客。请计算将所有乘客送至1号公交站所需的最少巴士数量。巴士不可重复访问同一站点，且容量无限。

原解法的问题 #

我之前的解法是统计所有路径中存在乘客的叶子节点数量，但存在重复计数问题：比如路径1-2-3和1-2-4，仅节点2有乘客时，我的解法会把两条路径都计入有效路径，导致结果错误。

原实现代码 #

void dfs(int curr, int parent, bool passInPath, int *resPointer, unordered_map<int, vector<int>> &adjmap, int passengers[])
{
    bool leaf = true;
    bool passenger = false;
    if (passInPath || passengers[curr])
    {
        passenger = true;
    }
    for (auto neigh : adjmap[curr])
    {
        if (neigh != parent && neigh != 1)
        {
            dfs(neigh, curr, passenger, resPointer, adjmap, passengers);
            leaf = false;
        }
    }
    if (leaf && passenger)
    {
        *resPointer = *resPointer + 1;
    }
   
}

int minBuses(int N, int passengers[], int edges[][2])
{
    // 构建邻接表
    unordered_map<int, vector<int>> adjmap;
    for (int i = 0; i < N-1; i++)
    {
        int e1 = edges[i][0];
        int e2 = edges[i][1];
        adjmap[e1].push_back(e2);
        adjmap[e2].push_back(e1);
    }

    int res = 0;
    int *resP = &res;

    // 从1号节点的每个邻居出发进行DFS
    for (auto neigh : adjmap[1])
    {
        dfs(neigh, 1, false, resP, adjmap, passengers);
    }

    return res;
}

正确解法思路 #

核心逻辑是统计1号节点需要派出巴士的独立分支数量：

• 巴士容量无限，所以每个分支（从1号出发的子树）只要存在需要接送的乘客，就只需要一辆巴士；若该分支下有多个子分支都存在乘客，每个子分支各需一辆巴士。
• 通过DFS遍历每个子树，返回该子树是否存在乘客（包括当前节点）。遍历过程中，统计当前节点的子节点中存在乘客的子树数量，每个对应一辆巴士。
• 如果当前节点自身有乘客且所有子节点都无乘客，该节点所在分支需要一辆巴士。

修改后的代码实现 #

// 返回当前子树是否存在需要接送的乘客
bool dfs(int curr, int parent, int *resPointer, unordered_map<int, vector<int>> &adjmap, int passengers[])
{
    bool hasPassenger = passengers[curr] == 1;

    // 遍历所有子节点（排除父节点）
    for (auto neigh : adjmap[curr])
    {
        if (neigh == parent) continue;
        
        bool childHasPassenger = dfs(neigh, curr, resPointer, adjmap, passengers);
        if (childHasPassenger)
        {
            // 子节点的子树有乘客，需要派一辆巴士
            (*resPointer)++;
            hasPassenger = true;
        }
    }

    return hasPassenger;
}

int minBuses(int N, int passengers[], int edges[][2])
{
    // 构建邻接表
    unordered_map<int, vector<int>> adjmap;
    for (int i = 0; i < N-1; i++)
    {
        int e1 = edges[i][0];
        int e2 = edges[i][1];
        adjmap[e1].push_back(e2);
        adjmap[e2].push_back(e1);
    }

    int res = 0;
    int *resP = &res;

    // 遍历1号节点的每个邻居
    for (auto neigh : adjmap[1])
    {
        bool childHasPassenger = dfs(neigh, 1, resP, adjmap, passengers);
        if (childHasPassenger)
        {
            (*resP)++;
        }
    }

    return res;
}

代码说明 #

1. DFS函数：返回当前子树是否存在乘客。遍历子节点时，若子节点的子树有乘客，则计数加1（需派一辆巴士去该子分支），同时标记当前子树有乘客。
2. 主函数：遍历1号节点的所有邻居，每个邻居的子树若有乘客，则计数加1。1号节点自身有乘客无需额外巴士，因为巴士从这里出发可直接搭载。
3. 解决原问题：针对示例中1-2-3、1-2-4且仅节点2有乘客的情况，DFS到节点2时，子节点3和4的子树都无乘客，节点2返回true，主函数中该分支计数加1，最终结果为1，符合预期。

内容的提问来源于stack exchange，提问作者snowcoffeebean