<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 edges[nbr] = 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.
*/

/*
To ENSURE edges[node] equals neighbor. This requires ensuring that
each node can only have one direct edge in the map, which might 
not be practical for multiple outgoing edges. So, if we need to flip
both edges of a node then edges[node] would give only one node which
is incorrect. So, use a set or find a simpler solution
*/

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        // edges stores the directed edges
        unordered_map<int, unordered_set<int>> edges;
        // nbrs stores the undirected edges for BFS traversal
        unordered_map<int, vector<int>> nbrs;
        vector<bool> visited(n, false);
        int ans = 0;

        // Populate the edges map with directed edges
        for (const auto& connection : connections) {
            edges[connection[0]].insert(connection[1]);
        }

        // Populate the adjacency list for undirected graph
        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 the directed edge exists from node to neighbor, it needs to be reordered
                    if (edges[node].count(neighbor)) {
                        ans++;
                    }
                    q.push(neighbor);
                    visited[neighbor] = true;
                }
            }
        }

        return ans;
    }
};

191673