1466. Reorder Routes to Make All Paths Lead to the City Zero

Link

Solution

Build 2 graphs with a different order, and calulate the count of using an invert order.

 int count = 0;
    public int minReorder(int n, int[][] connections) {
        List<Integer>[] graphOrg = new List[n];
        List<Integer>[] graphInvert = new List[n];
        for(int i = 0; i < n; i++){
            graphOrg[i] = new ArrayList<Integer>();
            graphInvert[i] = new ArrayList<Integer>();
        }
        
        for(int[] con : connections){
            graphInvert[con[0]].add(con[1]);
            graphOrg[con[1]].add(con[0]);
        }
        boolean[] isVisited = new boolean[n];
        dfs(graphOrg, graphInvert, 0, isVisited);
        return count;
    }
    
    
    public void dfs(List<Integer>[] graphOrg, List<Integer>[] graphInvert, int index, boolean[] isVisited){
        
        isVisited[index] = true;        
        for(int i : graphOrg[index]){
            if(isVisited[i]) continue;
            dfs(graphOrg, graphInvert, i, isVisited);
        }
        for(int i : graphInvert[index]){
            if(isVisited[i]) continue;
            count++;
            dfs(graphOrg, graphInvert, i, isVisited);
        }
    }