จัดเส้นทางใหม่ให้ทุกเส้นทางนำไปสู่เมืองศูนย์กลางใน C++

สมมติว่ามี n เมือง หมายเลข 0 ถึง n-1 และมี n-1 ถนน เชื่อมระหว่างเมืองคู่ใดคู่หนึ่งมีเพียงเส้นทางเดียว ถนนเป็น one-way เราต้องเปลี่ยนทิศทางถนนน้อยที่สุดเพื่อให้ทุกเมืองเดินทางไปยังเมือง 0 (เมืองหลวง) ได้

ตัวอย่าง: n=6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] ผลลัพธ์ = 3

วิธีแก้ปัญหา (BFS + Graph)

1. สร้าง graph1 (ทิศทางเดิม) และ graph2 (ทิศทางตรงข้าม)
2. BFS จากโหนด 0:
   • เดินตาม graph2 (ทิศทางถูกต้อง) cost = 0
   • เดินตาม graph1 (ต้องกลับทิศ) cost = 1
3. ใช้ Dijkstra แบบ 0-1 BFS (deque) หา cost รวมต่ำสุด
4. ผลรวม cost = จำนวนขอบที่ต้องกลับทิศ

ตัวอย่างโค้ด C++

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

const int N = 5e4 + 5; 

class Solution { 
public: 
    vector<int> graph1[N]; 
    vector<int> graph2[N]; 
    
    int minReorder(int n, vector<vector<int>>& e){ 
        for (auto& it : e) { 
            graph1[it[0]].push_back(it[1]); 
            graph2[it[1]].push_back(it[0]); 
        } 
        vector<int> dist(n, N + 10); 
        int ret = 0; 
        dist[0] = 0; 
        queue<int> q; 
        q.push(0); 
        set<int> visited; 
        visited.insert(0); 
        
        while (!q.empty()) { 
            int node = q.front(); q.pop(); 
            ret += dist[node]; 
            
            for (auto& it : graph2[node]) { 
                if (!visited.count(it) && dist[it] > 0) { 
                    dist[it] = 0; 
                    q.push(it); 
                    visited.insert(it); 
                } 
            } 
            for (auto& it : graph1[node]) { 
                if (!visited.count(it) && dist[it] > 1) { 
                    dist[it] = 1; 
                    q.push(it); 
                    visited.insert(it); 
                } 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<int>> v = {{0,1},{1,3},{2,3},{4,0},{4,5}}; 
    cout << (ob.minReorder(6,v)); 
}

ข้อมูลนำเข้า

6,{{0,1},{1,3},{2,3},{4,0},{4,5}}

ผลลัพธ์

3