Sắp xếp lại đường đi để tất cả dẫn về thành phố 0 (Reorder Routes) trong C++

Có n thành phố (0 đến n-1) và n-1 đường một chiều tạo thành cấu trúc cây. Cần đảo ngược hướng tối thiểu số đường để mọi thành phố đều có đường đến thành phố 0 (thủ đô).

Ví dụ

Đầu vào: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Đầu ra: 3 (đảo 3 cạnh).

Thuật toán BFS từ gốc 0

1. Xây dựng hai đồ thị: graph1[u] = các đỉnh v có cạnh u→v (hướng gốc), graph2[v] = các đỉnh u có cạnh u→v (hướng ngược).
2. BFS từ 0. Mảng dist lưu chi phí đến đỉnh: 0 nếu đi theo hướng ngược (đã đúng), 1 nếu phải đảo hướng.
3. Duyệt hàng đợi: ưu tiên đi theo cạnh ngược (cost 0) trước, sau đó cạnh xuôi (cost 1).
4. Tổng dist của tất cả đỉnh là số cạnh cần đảo.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    static const int N = 50005;
    vector<int> g1[N], g2[N];
public:
    int minReorder(int n, vector<vector<int>>& edges) {
        for (auto& e : edges) {
            g1[e[0]].push_back(e[1]);
            g2[e[1]].push_back(e[0]);
        }
        vector<int> dist(n, N);
        dist[0] = 0;
        queue<int> q; q.push(0);
        vector<bool> vis(n); vis[0] = true;
        int ans = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            ans += dist[u];
            for (int v : g2[u]) if (!vis[v] && dist[v] > 0) {
                dist[v] = 0; q.push(v); vis[v] = true;
            }
            for (int v : g1[u]) if (!vis[v] && dist[v] > 1) {
                dist[v] = 1; q.push(v); vis[v] = true;
            }
        }
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(N) - BFS duyệt mỗi cạnh/đỉnh một lần.
• Không gian: O(N) - đồ thị và mảng phụ.

Kết quả kiểm thử

Đầu vào: 6, {{0,1},{1,3},{2,3},{4,0},{4,5}}
Đầu ra: 3