[Med] LeetCode 1466. Reorder Routes to Make All Paths Lead to the City Zero

連接: https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/java

題目描述：
There are n cities numbered from 0 to n-1 and n-1 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.node

Roads are represented by connections where connections[i] = [a, b] represents a road from city a to b.web

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.api

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.數組

It’s guaranteed that each city can reach the city 0 after reorder.ide

Example 1:svg

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0this

Example 2:spa

Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).code

Example 3:

Input: n = 3, connections = [[1,0],[2,0]]
Output: 0

Constraints:

• 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]

Tag: Tree, DFS
解題思路
題目告訴咱們有n個城市，每兩個城市之間只有一條道路相連，而且這一條道路是一條有方向的道路。如今咱們要讓全部的城市均可以到達城市0 (到達指的是能夠通過0個或者多個有向道路到達)。問，咱們須要將多少條城市道路的方向調轉過來才能夠達到這樣的目的。題目當中能夠保證結果能夠出現。

由於題目中說，咱們保證兩個城市之間只有一條路能夠到達(這一條路能夠通過多個城市)。也就是說這裏實際上是一個有向無環的樹。咱們要作的就是從這棵樹的root (也就是城市0)出發，通過全部的子節點。若是在這個過程中父節點到子節點的路徑和給出的connections路徑相反的話，那麼咱們就須要轉換一次方向使得路徑是從父節點往子節點方向去的。每一次轉換咱們都將轉換的總次數加一，這樣咱們最後就會構成一個從root 爲0的樹，方向爲父節點指向子節點。由於咱們最後想要的結果是全部的子節點指向父節點的一棵樹，因此咱們最後還要用edge的總和，也就是n-1, 減去咱們累加出來的結果。纔是將全部節點指向root的須要轉換的次數。

爲了構成這棵樹，咱們首先構建一個無向圖。這個無向圖咱們使用hashmap來構造。兩個點之間互相有所鏈接。同時爲了在遍歷這個無向圖的時候快速定位這個方向和connections裏面的方向是否是對的。咱們再使用一個hashset，裏面存上城市原道路的方向 。這樣在遍歷咱們無向圖的時候就能夠快速的定位了。同時爲了不造成環，咱們再使用一個長度爲n的數組記錄咱們已經遍歷過的節點。

作完這些以後咱們從0節點出發。每一次咱們都從map當中獲取從source節點能夠到達的全部children節點。若是這個節點已經被visit過了，則跳過。不然若是當前咱們遍歷的兩個節點的方向沒有出如今direction hashset中，則增長total的值。

最後是返回n-1-total的值

TIME & SPACE: O(n)
解法一:

class Solution {
    int total =0;
    public int minReorder(int n, int[][] connections) {
        //注意不能添加新的edge
        Map<Integer, List<Integer>>  map = new HashMap<>();
        Set<String> direction = new HashSet<>();
        
        for(int[] connection : connections){
            int a = connection[0], b = connection[1];
            direction.add(a+"-"+b);

            if(!map.containsKey(b)) map.put(b, new ArrayList());
            if(!map.containsKey(a)) map.put(a, new ArrayList());
            map.get(a).add(b);
            map.get(b).add(a);
        }
        
        dfs(0, map, direction, new int[n]);
        return n-1-total;
    }
    
    public void dfs(int source, Map<Integer, List<Integer>> map, Set<String> direction, int[] visited){
        if(visited[source]==1) return;
        visited[source] = 1;
        
        for(int child : map.get(source)){
            if(visited[child]==1) continue;
            if(!direction.contains(source+"-"+child)){
                total++;
            }
            dfs(child, map, direction, visited);
        }
    }
}