力扣1466题：利用BFS解决有向图重排问题
一、题目解读
力扣1466题要求将一个有向图通过最小次数的“边重排”（即反转边方向）转化为一棵树。给定n个节点和m条边的有向图，需计算最少需要反转的边数，使图成为无环连通图（树）。题目需设计高效算法，避免暴力枚举所有边组合，需利用图论特性或搜索策略优化。
二、解题思路
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)，为图论优化问题的典型解法，适用于需快速处理有向图连通性的场景。
原创内容 转载请注明出处
