<p>There are <code>n</code> cities numbered from <code>0</code> to <code>n - 1</code> and <code>n - 1</code> roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.</p>

<p>Roads are represented by <code>connections</code> where <code>connections[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> represents a road from city <code>a<sub>i</sub></code> to city <code>b<sub>i</sub></code>.</p>

<p>This year, there will be a big event in the capital (city <code>0</code>), and many people want to travel to this city.</p>

<p>Your task consists of reorienting some roads such that each city can visit the city <code>0</code>. Return the <strong>minimum</strong> number of edges changed.</p>

<p>It&#39;s <strong>guaranteed</strong> that each city can reach city <code>0</code> after reorder.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/05/13/sample_1_1819.png" style="width: 311px; height: 189px;" />
<pre>
<strong>Input:</strong> n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
<strong>Output:</strong> 3
<strong>Explanation: </strong>Change the direction of edges show in red such that each node can reach the node 0 (capital).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/05/13/sample_2_1819.png" style="width: 509px; height: 79px;" />
<pre>
<strong>Input:</strong> n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
<strong>Output:</strong> 2
<strong>Explanation: </strong>Change the direction of edges show in red such that each node can reach the node 0 (capital).
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 3, connections = [[1,0],[2,0]]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>connections.length == n - 1</code></li>
	<li><code>connections[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
</ul>

/*
Do a Topo Sort to get the order of the graph.
Since all nodes want to point to 0 therefore, 0 must be the last
element of the ordering == Number of swaps needed in Topo Sort.

OR

Start bfs from 0 and then check the nbrs if they point correctly
else reverse the direction. Only count Outgoing Edges at every node.
*/
/*
        edges:
        nbrs: 
        0 > 1, 4
        1 > 3
        2 > 3
        3 > 1, 2
        4 > 0, 5
        5 > 4

        CONDITON OF FLIPPING IS nbr[node] = parent then don't flip
        */
/*
Data Structure BS:
For every Node we need to know if the Node can reach the city.
So we need to store the edge (from_i, to_i) for every node in a map.

Also, we need to get the neighbours for every node (un directionally)
so that we can check if the nbrs have edges towards or away from the
city 0 and thus we traverse.
*/

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        unordered_map<int, unordered_set<int>> edges;
        unordered_map<int, vector<int>> nbrs;
        vector<bool> visited(n, false);
        int ans = 0;

        // Create a set of directed edges
        for (const auto& connection : connections) {
            edges[connection[0]].insert(connection[1]);
        }

        // Create adjacency list for both directions
        for (const auto& connection : connections) {
            int from = connection[0];
            int to = connection[1];
            nbrs[from].push_back(to);
            nbrs[to].push_back(from);
        }

        // BFS to traverse the graph starting from node 0
        queue<int> q;
        q.push(0);
        visited[0] = true;

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

            for (int neighbor : nbrs[node]) {
                if (!visited[neighbor]) {
                    if (edges[node].count(neighbor)) {
                        ans++;
                    }
                    q.push(neighbor);
                    visited[neighbor] = true;
                }
            }
        }

        return ans;
    }
};

191673