思考:
面對有向圖 首先要將每一個點的關係掃入二為矩陣中
(紀錄 每一個點(0,1..., n) 可以到哪些點 可以被哪些點到)

1.題目是問 改變幾條連結 可以使得每一個點都能走到 0 點
2.connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
[0,1] 代表 0->1, 1<-0,
[1,3] 代表 1->3, 3<-1,.....
3.利用二維矩陣紀錄每個點能去的點 vector<vector<int>> gr(n);
4.用DFS遞迴從零點開始能關聯到的點

// to > 0 表示鐵路是指向別的城市(代表沒有指回0)，
// 因為是指向外面的點所以是正數會成立 >0 得到 1
change += dfs(gr, visited, abs(to)) + (to > 0);

class Solution {
public:
    // 使用深度優先搜索 (DFS) 來計算重新排列的次數
    int dfs(vector<vector<int>>& gr, vector<bool>& visited, int from) {
        int change = 0; 
        //change代表改變幾條點和點連結可以使得全部的點都能走到0
        //change用於記錄改變的次數。每次DFS時，如果存在一個和當前點沒有連接的，就會+1，代表需要改幾次才能全部連通到0。
        visited[from] = true;  // 標記目前的城市已經被訪問
        //掃描每一個點可以到的點
        for (auto to : gr[from]) {
            //如果這個點還沒有去過 但是可以去
            if (!visited[abs(to)]) {
                // to > 0 表示鐵路是指向別的城市(代表沒有指回0)，遞迴到最底部時會=1造成change+1，因為需要改變方向 
                change += dfs(gr, visited, abs(to)) + (to > 0);
            }   
        }
        return change;
    }
    
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<int>> gr(n);  // 用於存儲城市之間的鐵路關係
        for (auto &c : connections) {
            // 建立城市之間的鐵路關係，正向表示鐵路指向新城市，負向表示鐵路指向舊城市
            gr[c[0]].push_back(c[1]);   
            gr[c[1]].push_back(-c[0]);
                                        //gr[0] = {1, -4}
                                        //gr[1] = {-0, 3}
                                        //gr[2] = {3}
                                        //gr[3] = {-1, -2}
                                        //gr[4] = {0, 5}
                                        //gr[5] = {-4}
        }
        vector<bool>v(n, false);
        // 使用 DFS 遞迴來計算重新排列的次數，初始為 0
        return dfs(gr, v, 0);
    }
};

class Solution {
public:
    int dfs(int node, const vector<vector<int>>& dir, vector<bool>& vis){
        int count = 0;
        vis[node] = true;
        for(auto i : dir[node]){
            if(vis[abs(i)] == false){
                count = count + dfs(abs(i), dir, vis) + (i > 0);
            }
        }
        return count;
    }


    int minReorder(int n, vector<vector<int>>& connections) {
        //記錄每個點的連接情況
        vector<vector<int>> dir(n);
        //每個點的拜訪情況, 預設都未拜訪
        vector<bool> vis(n, false);
        //掃 connections 內的每一個元素
        for(auto& i : connections){
            dir[i[0]].push_back(i[1]);
            dir[i[1]].push_back(-i[0]);
        }
        //從 0 出發 
        return dfs(0, dir, vis);
    }
};

class Solution {
public:

// connections = [[1,0],[1,2],[3,2],[3,4]]

// edge[0] = -1, 
// edge[1] = 0, 2
// edge[2] = -1, -3
// edge[3] = 2, 4
// edge[4] = -3

// 1th start = 0; let v[0] = t, if(v[1] == false) -> change += DFS(edge, vis, 1) + (i(-1)>0);// 2 ans.
// 2th start = 1; let v[1] = t, if(v[0] == false)xx
//                              if(v[2] == false) -> change += DFS(edge, vis, 2) + (i(2)>0); // 1 + 0 + 1
// 3th start = 2; let v[2] = t, if(v[1] == false)xx
//                              if(v[3] == false) -> change += DFS(edge, vis, 3) + (i(-3) >0 );// 1
// 4th start = 3; let v[3] = t, if(v[2] == false)xx
//                              if(v[4] == false) -> change += DFS(edge, vis, 4) + (i(4) > 0); // 0 + 0 + 1 =1
// 5th start = 4, let v[4] = t, if(v[3] == fasle) xx return change = 0


    int DFS(vector<vector<int>>& edge, vector<bool>& vis, int start){
        //紀錄要改變幾條路徑才可以
        int change = 0; 
        vis[start] = true;
        //從start向外遞迴跟這個點有關的點
        for(auto i : edge[start]){
            if(vis[abs(i)] == false){
                //拜訪還沒去過的點
                // (i >= 0) 代表的是這個點指向的是外面 所以至少要改掉這邊 (+1)
                change += DFS(edge, vis, abs(i)) + (i >= 0);
            }
        }
        return change;
    }


    int minReorder(int n, vector<vector<int>>& connections) {
        //先記錄每個邊的情況
        vector<vector<int>> edge(n);
        //紀錄哪些點已經被拜訪過
        vector<bool>v(n, false);
        for(auto i : connections){
            //因為是從i[0]~i[1] 正向關係
            edge[i[0]].push_back(i[1]);
            //因為是從i[1]~i[0] 反向關係
            edge[i[1]].push_back(-i[0]);
        }
        // 0 是起點 也可以計算到其他點要改變的邊 
        return DFS(edge, v, 0);
    }
};