1601. Maximum Number of Achievable Transfer Requests

Question

We have n buildings numbered from 0 to n - 1. Each building has a number of employees. It’s transfer season, and some employees want to change the building they reside in.

You are given an array requests where requests[i] = [fromi, toi] represents an employee’s request to transfer from building fromi to building toi.

All buildings are full, so a list of requests is achievable only if for each building, the net change in employee transfers is zero. This means the number of employees leaving is equal to the number of employees moving in. For example if n = 3 and two employees are leaving building 0, one is leaving building 1, and one is leaving building 2, there should be two employees moving to building 0, one employee moving to building 1, and one employee moving to building 2.

Return the maximum number of achievable requests.

Solution

我的思路：根据人员流动建立有向图，然后回溯求所有的环。再用回溯求边数允许的最多环。

更好的思路：直接回溯，用一个数组记录节点的流出及流入。

当回溯到最后时，如果所有节点流出流入平衡（为0）时，则可以将其长度计入。

Code

class Solution {
    public int maximumRequests(int n, int[][] requests) {
        return backtrack(new int[n], requests, 0, 0);
    }

    private int backtrack(int[] count, int[][] requests, int i, int len){
        if(i >= requests.length) {
            if(isAcceptable(count)) return len;
            return 0;
        }
        int not = backtrack(count, requests, i+1, len);
        count[requests[i][0]]--;
        count[requests[i][1]]++;
        int select = backtrack(count, requests, i+1, len+1);
        count[requests[i][0]]++;
        count[requests[i][1]]--;
        return Math.max(not, select);
    }

    private boolean isAcceptable(int[] count){
        for(int i : count){
            if(i != 0) return false;
        }
        return true;
    }
}

class Solution {
    boolean[] visited;
    boolean[] inCycle;
    int len;
    int[][] g;
    List<Integer> tempCycle;
    int res;
    List<List<Integer>> cycles;
    public int maximumRequests(int n, int[][] requests) {
        visited = new boolean[n];
        inCycle = new boolean[n];
        len = n;
        g = new int[n][n];
        tempCycle = new ArrayList<Integer>();
        res = 0;
        cycles = new ArrayList<>();
        for(int i = 0; i < requests.length; i++){   // Build Graph
            int from = requests[i][0];
            int to = requests[i][1];
            g[from][to]++;
        }
        for(int i = 0; i < n; i++){ // Get All Cycles
            if(!visited[i]) getCycles(i, tempCycle);
        }
        res = getLongestCycle(0, 0);    // Get Longest Selection
        return res;
    }

    private int getLongestCycle(int c, int length){
       if(c >= cycles.size()) return length;
        boolean isSelect = true;
        int select = Integer.MIN_VALUE;
        List<Integer> cycle = cycles.get(c);
        for(int i = 0; i < cycle.size()-1; i++){
            if(g[cycle.get(i)][cycle.get(i+1)] <= 0){
                isSelect = false;
                break;
            }
        }
        if(isSelect){
            for(int i = 0; i < cycle.size()-1; i++){
                g[cycle.get(i)][cycle.get(i+1)]--;
            }
            select = getLongestCycle(c+1, length + cycle.size()-1);
            for(int i = 0; i < cycle.size()-1; i++){
                g[cycle.get(i)][cycle.get(i+1)]++;
            }
        }
        int not = getLongestCycle(c+1, length);
        return Math.max(not, select);
    }

    private void getCycles(int from, List<Integer> tempCycle){
        inCycle[from] = true;
        visited[from] = true;
        tempCycle.add(from);
        for(int to = 0; to < len; to++){
            if(g[from][to] > 0){
                for(int i = 0; i <g[from][to]; i++){
                    if(!inCycle[to]){
                        getCycles(to, tempCycle);
                    }
                    else{
                        int start = tempCycle.indexOf(to);
                        List<Integer> cycle = new ArrayList<Integer>();
                        for (int j = start; j < tempCycle.size(); j++) {
                            cycle.add(tempCycle.get(j));
                        }
                        cycle.add(tempCycle.get(start));
                        cycles.add(cycle);
                    }
                }
            }
        }
        inCycle[from] = false;
        tempCycle.remove(tempCycle.size()-1);
    }
}