今日份題目：
n 座城市，從 0 到 n-1 編號，其間共有 n-1 條路線。因此，要想在兩座不同城市之間旅行只有唯一一條路線可供選擇（路線網形成一顆樹）。去年，交通運輸部決定重新規劃路線，以改變交通擁堵的狀況。
路線用 connections 表示，其中 connections[i] = [a, b] 表示從城市 a 到 b 的一條有向路線。
今年，城市 0 將會舉辦一場大型比賽，很多游客都想前往城市 0 。
請你幫助重新規劃路線方向，使每個城市都可以訪問城市 0 。返回需要變更方向的最小路線數。
題目數據 保證 每個城市在重新規劃路線方向后都能到達城市 0 。
示例1
輸入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] 輸出：3 解釋：更改以紅色顯示的路線的方向，使每個城市都可以到達城市 0 。
示例2
輸入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] 輸出：2 解釋：更改以紅色顯示的路線的方向，使每個城市都可以到達城市 0 。
示例3
輸入：n = 3, connections = [[1,0],[2,0]] 輸出：0
提示
-
2 <= n <= 5 * 10^4 -
connections.length == n-1 -
connections[i].length == 2 -
0 <= connections[i][0], connections[i][1] <= n-1 -
connections[i][0] != connections[i][1]
題目思路
這道題我們使用bfs廣度優先遍歷。拿例1為例，我們只需要從0開始遍歷，由于路徑單向通行，故與這些點的連線都需要反向，除此之外，下邊那條邊直接找是無法從0走過去的，但還有條路需要反向，這時，我們引入反向圖，在正向bfs的同時對反向圖同樣bfs，放入同一個隊列中，這樣就可以保證圖中所有不滿足條件的邊都被記錄下來了。
所謂反向圖，就是將圖中所有的路徑反向，（i，j）處的值與（j，i）處的值交換。
代碼
class Solution
{
public:int minReorder(int n, vector<vector<int>>& connections) {vector<vector<int> > graph(n);//正向圖vector<vector<int> > antigraph(n);//反向圖for(auto& c:connections) {graph[c[0]].push_back(c[1]);//記錄正向圖antigraph[c[1]].push_back(c[0]);//記錄反向圖}int ans=0;int visited[100000]={0};visited[0]=1;queue<int> p;p.push(0);//bfswhile(!p.empty()) {//獲取當前點信息int i=p.front();p.pop();//正向遍歷搜尋結果for(int j=0;j<graph[i].size();j++){if(visited[graph[i][j]]==0) {visited[graph[i][j]]=1;//標記為已到達過ans++;//0向外能到達的點的路徑就是需要反向的路徑p.push(graph[i][j]);}}//反向遍歷搜尋結果for(int j=0;j<antigraph[i].size();j++){if(visited[antigraph[i][j]]==0) {visited[antigraph[i][j]]=1;//標記為已到達過p.push(antigraph[i][j]);} } }return ans;}
};
提交結果
?歡迎大家在評論區討論，如有不懂的代碼部分，歡迎在評論區留言！
