1
class Solution {
2
 public:
3
  vector<int> Radj[50001], adj[50001], visited;
4
  int bfs() {
5
    int edges = 0;
6
    queue<int> q;
7
    q.push(0);
8

9
    while (q.size()) {
10
      auto src = q.front();
11
      q.pop();
12
      visited[src] = 1;
13

14
      for (auto &nbr : adj[src]) {
15
        if (visited[nbr]) continue;
16
        // this connection needs reverse orientation
17
        ++edges;
18
        q.push(nbr);
19
      }
20

21
      for (auto &nbr : Radj[src]) {
22
        if (visited[nbr]) continue;
23
        q.push(nbr);
24
      }
25
    }
26

27
    return edges;
28
  }
29
  int minReorder(int n, vector<vector<int>> &connections) {
30
    visited.resize(n, 0);
31
    for (auto &x : connections) adj[x[0]].push_back(x[1]), Radj[x[1]].push_back(x[0]);
32
    return bfs();
33
  }
34
};