# Leetcode 1466. Reorder Routes to Make All Paths Lead to the City Zero
###### tags: `leetcode` `daily` `BFS`

[題目連結](https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/)

# Method BFS
:::info
:bulb: **作法講解**:
because we start from node 0,
so we can split road into two situation,
case 1: node 1 -> node 0
We don't need reorder this path.

case 2: node 0 -> node 1
we need to reorder this path.

using adj to record above sitation.
if the road is `v[0] -> v[1]`

`adj[v[0]] = {v[1], 1}`
`adj[v[1]] = {v[0], 0}`

first value is destination,
if second value is 1, we need to reorder this path,
if second value is 0, we don't need to reorder this path.

after adj variable is ready,
we can use queue "q" to record the node we reached.
and we can use vector "visited" to record which node we visited.

Initailize, "q" has node 0. "visited[0] = true"
it means we start from node 0,

we can using "adj" to scan all of the node,
if the second value of the node is 1,
we need increase output by 1.
:::

TC: O(N) SC: O(N)
完整程式碼

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> adj(n);
        vector<bool> visited(n, false);
        queue<int> q;
        int output = 0;


        for(vector<int> &v : connections) {
            adj[v[0]].push_back({v[1], 1});
            adj[v[1]].push_back({v[0], 0});
        }

        q.push(0);
        visited[0] = true;

        while(!q.empty()) {
            int node = q.front();
            q.pop();

            for(int j = 0 ; j < adj[node].size(); j++) {
                int next = adj[node][j].first;
                int val = adj[node][j].second;
                
                if(visited[next]) {
                    continue;
                }

                visited[next] = true;
                output += val;
                q.push(next);
            }
        }
        return output;
    }
};