题目描述

声明：只是记录一下code 没写题解 详见leetcode评论区

样例

Input: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
Output: 5
Explantion: Let's see the requests:
From building 0 we have employees x and y and both want to move to building 1.
From building 1 we have employees a and b and they want to move to buildings 2 and 0 respectively.
From building 2 we have employee z and they want to move to building 0.
From building 3 we have employee c and they want to move to building 4.
From building 4 we don't have any requests.
We can achieve the requests of users x and b by swapping their places.
We can achieve the requests of users y, a and z by swapping the places in the 3 buildings.

算法1

(枚举然后检验) $O((N + R) * 2^R)$

Python3 代码

def maximumRequests(self, n, req):
        for k in range(len(req), 0, -1):
            for c in itertools.combinations(range(len(req)), k):
                degree = [0] * n
                for i in c:
                    degree[req[i][0]] -= 1
                    degree[req[i][1]] += 1
                if not any(degree):
                    return k
        return 0

算法2

Python3 代码

def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        nr = len(requests)
        res = 0

        def test(mask):
            outd = [0] * n
            ind = [0] * n
            for k in range(nr):
                if (1 << k) & mask:
                    outd[requests[k][0]] += 1
                    ind[requests[k][1]] += 1
            return sum(outd) if outd == ind else 0

        for i in range(1 << nr):
            res = max(res, test(i))
        return res

摘自评论区lee