1、图论

找到小镇的法官

在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。

如果小镇的法官真的存在，那么：

小镇的法官不相信任何人。
每个人（除了小镇法官外）都信任小镇的法官。
只有一个人同时满足属性 1 和属性 2 。
给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的标记。否则，返回 -1。

示例 1：

输入：N = 2, trust = [[1,2]]
输出：2
示例 2：

输入：N = 3, trust = [[1,3],[2,3]]
输出：3
示例 3：

输入：N = 3, trust = [[1,3],[2,3],[3,1]]
输出：-1
示例 4：

输入：N = 3, trust = [[1,2],[2,3]]
输出：-1
示例 5：

输入：N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
输出：3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-town-judge

class Solution(object):

    def findJudge(self, N, trust):

        """

        :type N: int

        :type trust: List[List[int]]

        :rtype: int

        """

        if not trust:

            if N == 0:

                return -1

            elif N == 1:

                return 1

            else:

                return -1

        believe_dict = collections.defaultdict(list)

        believed_dict = collections.defaultdict(list)

        max_count = 0

        result_id = -1

        for p1, p2 in trust:

            believe_dict[p2].append(p1)

            believed_dict[p1].append(p2)

        for i in range(1, N + 1):

            if max_count < len(believe_dict[i]):

                max_count = len(believe_dict[i])

                result_id = i

        if max_count == N - 1 and not believed_dict.get(result_id):

            return result_id

        return -1

2、图的遍历

岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-area-of-island

class Solution(object):

    def maxAreaOfIsland(self, grid):

        """

        :type grid: List[List[int]]

        :rtype: int

        """

        if not grid:

            return

        def solution_by_bfs():

            max_area = 0

            def bfs(x, y, grid):

                queue = [(x, y)]

                sums = 0

                while queue:

                    new_queue = []

                    for i, j in queue:

                        if grid[i][j] != 1:

                            continue

                        grid[i][j] = 0

                        sums += 1

                        for next_i, next_j in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:

                            if 0 <= next_i < len(grid) and 0 <= next_j < len(grid[0]) and grid[next_i][next_j] == 1:

                                new_queue.append((next_i, next_j))

                    queue = new_queue

                return sums

            for i in range(len(grid)):

                for j in range(len(grid[0])):

                    if grid[i][j] == 1:

                        max_area = max(max_area, bfs(i, j, grid))

            return max_area

        def solution_by_dfs(grid):

            max_area = 0

            def dfs(i, j, sum, grid):

                if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == 1:

                    grid[i][j] = 0

                    sum[0] += 1

                    dfs(i, j - 1, sum, grid)

                    dfs(i, j + 1, sum, grid)

                    dfs(i - 1, j, sum, grid)

                    dfs(i + 1, j, sum, grid)

            for i in range(len(grid)):

                for j in range(len(grid[0])):

                    sum = [0]

                    dfs(i, j, sum, grid)

                    max_area = max(max_area, sum[0])

            return max_area

        # return solution_by_dfs(grid)

        return solution_by_bfs(grid)

3、图的最短路径

访问所有节点的最短路径

给出 graph 为有 N 个节点（编号为 0, 1, 2, ..., N-1）的无向连通图。

graph.length = N，且只有节点 i 和 j 连通时，j != i 在列表 graph[i] 中恰好出现一次。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

示例 1：

输入：[[1,2,3],[0],[0],[0]]
输出：4
解释：一个可能的路径为 [1,0,2,0,3]
示例 2：

输入：[[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一个可能的路径为 [0,1,4,2,3]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes

class Solution(object):

    def shortestPathLength(self, graph):

        """

        :type graph: List[List[int]]

        :rtype: int

        """

        n = len(graph)

        lelvel = 0

        target = (1 << n) - 1

        queue = [(i, 1 << i) for i in range(n)]

        dist = set()

        while queue:

            new_queue = []

            for node, state in queue:

                if state == target:

                    return lelvel

                for next_node in graph[node]:

                    new_state = state | (1 << next_node)

                    if (next_node, new_state) not in dist:

                        dist.add((next_node, new_state))

                        new_queue.append((next_node, new_state))

            queue = new_queue

            lelvel += 1

        return lelvel

4、图的搜索

朋友圈

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:

输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/friend-circles

class Solution(object):

    def findCircleNum(self, M):

        """

        :type M: List[List[int]]

        :rtype: int

        """

        def dfs(M, visited, i):

            for j in range(len(M)):

                if M[i][j] == 1 and visited[j] == 0:

                    visited[j] = 1;

                    dfs(M, visited, j)

#         visited = [0 for x in range(len(M))]  # 行搜索

#         count = 0

#         for i in range(len(M)):

#             if visited[i] == 0:

#                 dfs(M, visited, i);

#                 count += 1

#         return count

        def bfs(M):

            queue = set()

            visited = [0]*len(M)  # 行搜索

            count = 0

            for i in range(len(M)):

                if visited[i] == 1:

                    continue

                queue.add(i)

                while queue:

                    new_queue = set()

                    for s in queue:

                        visited[s] = 1

                        for j in range(len(M)):

                            if M[s][j] == 1 and visited[j] == 0:

                                new_queue.add(j)

                    queue = new_queue

                count += 1

            return count

        return bfs(M)

        def find_num(M):  # 并查集

            def find(parent, i):

                if parent[i] == -1:

                    return i

                return find(parent, parent[i])

            def union(parent, x, y) :

                xset = find(parent, x)

                yset = find(parent, y)

                if xset != yset:

                    parent[xset] = yset

            parent = [-1 for x in range(len(M))]

            for i in range(len(M)):

                for j in range(len(M)):

                    if M[i][j] == 1 and i != j:

                        union(parent, i, j)

            count = 0

            print(parent)

            for i in range(len(parent)):

                if parent[i] == -1:

                    count += 1

            return count

        # return find_num(M)

巴特西

leetcode刷题（三）