LeetCode 每日一题 Day 4_代码007(未授权)

本文介绍: 给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n – 1 ，且恰好有 n – 1 条路。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条双向路。输入：roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], s e a ts = 2。输入：roads = [[0,1],[0,2],[0,3]], s e a t s = 5。解释：没有代表需要从别的城市到达首都。

给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n – 1 ，且恰好有 n – 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条双向路。

每个城市里有一个代表，他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 s e a t s 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

示例 1：
在这里插入图片描述

class Solution {
public:
    long long minimumFuelCost(vector<vector<int&gt;&gt; &amp;roads, int seats) {
        vector<vector<int&gt;&gt; adjacencyList(roads.size() + 1);

        // 构建邻接表
        for (auto &amp;edge : roads) {
            int city1 = edge[0], city2 = edge[1];
            adjacencyList[city1].push_back(city2);
            adjacencyList[city2].push_back(city1);
        }

        long long totalFuel = 0;

        function<int(int, int)&gt; dfs = [&amp;](int currentCity, int parentCity) -&gt; int {
            int subtreeSize = 1;
//lambda表达式
            // 遍历邻居节点
            for (int neighbor : adjacencyList[currentCity]) {
                if (neighbor != parentCity) {
                    subtreeSize += dfs(neighbor, currentCity);
                }
            }

            // 如果当前城市不是根节点，计算需要的油耗
            if (currentCity != 0) {
                totalFuel += (subtreeSize - 1) / seats + 1; 
            }

            return subtreeSize;
        };

        dfs(0, -1); // 从根节点开始深度优先搜索
        return totalFuel;
    }
};