C++ | DFS with explanation
Assume each city can reach the city 0, then from the city 0, it can always reach all the cities if the connections are all reversed. Then we can traverse this r
Assume each city can reach the city 0, then from the city 0, it can always reach all the cities if the connections are all reversed. Then we can traverse this reversed directed-graph and check each connection without repeatation, we can get the minimum number of edges to change by counting the connection that can be found in "connections".\n\nUse the example from the description as below, the desired changes of the connections are shown in red. After changing, it becomes a directed-graph connection each leave to the centroid, namely the city 0. Assume we can flip the connection here, then the graph becomes a directed graph from city 0 to each leave.\n\nBy traversing from the centroid, the city 0, it goes through each connection but with the opposite direction. Once you find any connection is along with your moving direction then it should be counted.\n\n![image](https://assets.leetcode.com/users/images/4669f6ab-79c3-4973-8088-81417c2ea60f_1615330991.3952718.png)\n\nIt is straight forward to use DFS to traverse the graph here.\n\nThe code is as below.\n\n```\nclass Solution {\npublic:\n    int minReorder(int n, vector<vector<int>>& connections) {\n        // build undirected graph\n        vector<vector<int>> graph(n);\n        for(auto& conn : connections) {\n            graph[conn[0]].push_back(conn[1]);\n            graph[conn[1]].push_back(conn[0]);\n        }\n        \n        // set\n        set<vector<int>> conn_set(connections.begin(), connections.end());\n        \n        // dfs\n        int ans = 0;\n        vector<bool> visited(n);\n        dfs(graph, conn_set, visited, 0, ans);\n        \n        return ans;\n    }\n    \n    void dfs(vector<vector<int>>& graph, set<vector<int>>& conn_set, vector<bool>& visited, int cur, int& ans) {\n        if(visited[cur]) return;\n        \n        visited[cur] = true;\n\n        for(int next : graph[cur]) {          \n            if(!visited[next]) {\n                if(conn_set.count({cur, next})) {\n                    ans += 1;\n                }\n                dfs(graph, conn_set, visited, next, ans);\n            }\n        }\n    }\n};\n```
[]