一、题目解读

力扣1466题要求将一个有向图通过最小次数的“边重排”（即反转边方向）转化为一棵树。给定n个节点和m条边的有向图，需计算最少需要反转的边数，使图成为无环连通图（树）。题目需设计高效算法，避免暴力枚举所有边组合，需利用图论特性或搜索策略优化。

二、解题思路

采用广度优先搜索（BFS）结合方向标记的解法，核心思想：

1. 构建邻接表存储边信息，每条边附带方向标记（原始方向/反向）。

2. 从节点0开始BFS遍历图，检查每条边的方向：

○ 若边方向与原图一致（is_original = true），且目标节点未访问，则需反转该边才能形成树，累加反转次数。

○ 若边方向为反向（is_original = false），则直接遍历。

3. 遍历完成后，若所有节点均被访问，说明图可转化为树，返回反转次数；否则无解。

关键在于通过方向标记区分原边与反向边，利用BFS确保树的连通性，避免无效遍历。

三、解题步骤

1. 构建邻接表：

○ 初始化graph为n个空列表，存储节点的出边信息。

○ 遍历connections，对每条边(u, v)：

■ 添加(u, v, true)到graph[u]，表示原方向边；

■ 添加(v, u, false)到graph[v]，表示反向边。

2. 初始化BFS：

○ 标记节点0已访问，将其入队。

3. BFS遍历：

○ 循环直至队列为空，当前节点u出队。

○ 遍历u的所有出边(v, is_original)：

■ 若v未访问，分情况处理：

● 若is_original = true（原方向边），说明需反转边才能形成树，累加反转次数res；

● 若is_original = false（反向边），则无需操作。

■ 标记v已访问，将其入队。

4. 结果检查：遍历结束后，若所有节点均被访问，返回res；否则题目无解（图中存在环或未连通）。

四、代码与注释

class Solution {public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, bool>>> graph(n); // 邻接表，bool表示方向是否原样
        for (auto& conn : connections) {
            graph[conn[0]].emplace_back(conn[1], true);  // 原始方向
            graph[conn[1]].emplace_back(conn[0], false); // 反向边
        }
        
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(0);
        visited[0] = true;
        int res = 0;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (auto& [v, is_original] : graph[u]) {
                if (!visited[v]) {
                    if (is_original) res++; // 需要反转的边
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        return res;
    }};

注释说明：

● graph[u].emplace_back(v, true)：存储原方向边，标记为true；

● if (is_original) res++：当BFS遇到原方向边时，说明该边需反转才能形成树；

● BFS遍历确保树的连通性，方向标记避免重复判断边方向。

五、总结

本文通过BFS算法高效解决有向图重排边问题。核心创新点：

1. 邻接表记录边方向，简化反转判断逻辑；

2. BFS保证遍历顺序，避免环检测的开销；

3. 仅统计原方向边的反转次数，无需验证最终图是否为树。

算法时间复杂度O(n+m)，空间复杂度O(n+m)，为图论优化问题的典型解法，适用于需快速处理有向图连通性的场景。

来源：力扣题解