力扣2858题：从BFS到动态规划巧解有向图

2天前力扣题解42

一、问题理解

给定一个有向图，如果将所有边视为无向边，则图形成一棵树。我们需要为每个节点计算，以该节点为根时，最少需要反转多少条边的方向，才能从该节点到达所有其他节点。

二、解题思路

‌树的性质‌：由于无向图是一棵树，所以任意两点之间有且只有一条路径。
‌关键观察‌：从根节点到子节点的边方向决定了是否需要反转。
‌递推关系‌：相邻节点的反转次数可以通过父节点的反转次数推导出来。

三、算法详解

‌构建邻接表‌：

存储每个节点的邻居，并标记边的方向（原始方向或反向）

‌第一次BFS‌：

以节点0为根，计算从0出发到达所有节点需要的反转次数
遇到反向边时增加反转计数

‌第二次BFS‌：

利用递推关系计算其他节点为根时的反转次数
对于边u->v（原始方向），res[v] = res[u] + 1
对于边v->u（反向边），res[v] = res[u] - 1

‌返回结果‌：

存储每个节点作为根时的最少反转次数

四、完整代码

class Solution {
public:
    vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
        // 构建邻接表，同时记录边的方向
        vector<vector<pair<int, bool>>> adj(n);
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            adj[u].emplace_back(v, true);  // 原始方向
            adj[v].emplace_back(u, false); // 反向边
        }

        // 第一次BFS，计算以0为根时的反转次数
        vector<int> res(n, 0);
        queue<int> q;
        vector<bool> visited(n, false);
        q.push(0);
        visited[0] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto& [v, dir] : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    if (!dir) { // 如果是反向边，需要反转
                        res[0]++;
                    }
                    q.push(v);
                }
            }
        }

        // 第二次BFS，计算其他节点为根时的反转次数
        q.push(0);
        fill(visited.begin(), visited.end(), false);
        visited[0] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto& [v, dir] : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    // 关键递推公式
                    res[v] = res[u] + (dir ? 1 : -1);
                    q.push(v);
                }
            }
        }

        return res;
    }
};