C++刷leetcode（1466. 重新规划路线）【深度优先搜索】【有向图】

糖逗

题目描述：

1. n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。
   
2. 
   
3. 路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。
   
4. 
   
5. 今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。
   
6. 
   
7. 请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。
   
8. 
   
9. 题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。
   
10. 
    
11.  
    
12. 
    
13. 示例 1：
    
14. 
    
15. 
    
16. 
    
17. 输入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
    
18. 输出：3
    
19. 解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。
    
20. 示例 2：
    
21. 
    
22. 
    
23. 
    
24. 输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
    
25. 输出：2
    
26. 解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。
    
27. 示例 3：
    
28. 
    
29. 输入：n = 3, connections = [[1,0],[2,0]]
    
30. 输出：0
    
31.  
    
32. 
    
33. 提示：
    
34. 
    
35. 2 <= n <= 5 * 10^4
    
36. connections.length == n-1
    
37. connections[i].length == 2
    
38. 0 <= connections[i][0], connections[i][1] <= n-1
    
39. connections[i][0] != connections[i][1]
    
40. 
    
41. 来源：力扣（LeetCode）
    
42. 链接：https://leetcode-cn.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero
    
43. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     void dfs(int node, int parent, map<int, vector<pair<int, bool> > >& store, int& res){
   
4.         if(node != 0 && store[node].size() == 1) return;
   
5.         for(auto cha : store[node]){
   
6.             if(cha.first != parent){//去除自环的情况
   
7.                 if(cha.second == true) res++;
   
8.                 cout  << cha.first << endl;
   
9.                 dfs(cha.first, node, store, res);
   
10.             }
    
11.         }
    
12.     }
    
13.     int minReorder(int n, vector<vector<int>>& connections) {
    
14.         //在建立无向邻接信息的基础上添加指向的bool型数据，构建邻接信息
    
15.         map<int, vector<pair<int, bool> > > store;
    
16.         for(auto cha : connections){
    
17.             store[cha[0]].push_back(make_pair(cha[1], true));
    
18.             store[cha[1]].push_back(make_pair(cha[0], false));
    
19.         }
    
20.         //深度优先搜索
    
21.         int res = 0;
    
22.         dfs(0, -1, store, res);
    
23.         return res;
    
24.     }
    
25. };

复制代码

糖逗

参考评论区想法改写的