# -*- coding: utf-8 -*-
"""
 @Time    : 2020/7/16 8:49
 @Author  : QDY
 @FileName: 785. 判断二分图.py

    给定一个无向图graph，当这个图为二分图时返回true。
    如果我们能将一个图的节点集合分割成两个独立的子集A和B，
    并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
    graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。
    每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

    示例 1:
    输入: [[1,3], [0,2], [1,3], [0,2]]
    输出: true
    解释:
    无向图如下:
    0----1
    |    |
    |    |
    3----2
    我们可以将节点分成两组: {0, 2} 和 {1, 3}。

    示例 2:
    输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
    输出: false
    解释:
    无向图如下:
    0----1
    | \  |
    |  \ |
    3----2
    我们不能将节点分割成两个独立的子集。

    注意:
    graph 的长度范围为 [1, 100]。
    graph[i] 中的元素的范围为 [0, graph.length - 1]。
    graph[i] 不会包含 i 或者有重复的值。
    图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

"""


class Solution:
    def isBipartite(self, graph):
        mark = {}
        # def dfs(node):
        #     for neighbor in graph[node]:
        #         if neighbor not in mark:
        #             mark[neighbor] = not mark[node]
        #             if not dfs(neighbor):
        #                 return False
        #         elif mark[neighbor]==mark[node]:
        #             return False
        #     return True
        for i in range(len(graph)):  # 遍历每个节点
            if i not in mark:  # 没标记过的节点，标记为True
                mark[i] = True
                # if not dfs(i):
                #     return False
                stack = [i]
                while stack:  # dfs
                    node = stack.pop()
                    for neighbor in graph[node]:
                        if neighbor not in mark:  # 若邻节点为被标记
                            mark[neighbor] = not mark[node]  # 用与该节点相反的标记
                            stack.append(neighbor)  # 加入栈中，下个循环中取出，深度遍历
                        elif mark[neighbor] == mark[node]:  # 该节点与其邻节点标记相同
                            return False  # 说明存在奇数个节点的环，返回False
        return True
