886.可能的二分法

https://leetcode-cn.com/problems/possible-bipartition/

一、二分图

将dislikes数组理解为边，人理解为两端的顶点，问题转化为求是否存在二分图

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        self.flag = True
        visited = [False] * (n+1)
        color = [False] * (n+1)
        graph = {}
        for i in range(1, n+1):
            graph[i] = list()
        # 通过边构建邻接表
        for edge in dislikes:
            f = edge[0]
            t = edge[1]
            # 无向图也是双向图
            graph[f].append(t)
            graph[t].append(f)

        def dfs(v):
            if not self.flag:
                return
            visited[v] = True
            for j in graph[v]:
                if not visited[j]:
                    color[j] = not color[v]
                    dfs(j)
                else:
                    if color[j] == color[v]:
                        self.flag = False

        for i in range(1, n+1):
            if not visited[i]:
                dfs(i)
        return self.flag