BFS/DFS/拓扑排序 模板题Python代码

互联网 2021/9/15 12:04:48

LC785.判断二分图 LeetCode 785 方法一: BFS + 染色 class Solution:def isBipartite(self, graph: List[List[int]]) -> bool:# BFSfrom collections import dequen = len(graph)UNCOLORED, RED, GREEN = 0, 1, 2color = [UNCOLORED]*n # 暂时标记为颜色0# 颜色: 0…

LC785.判断二分图 LeetCode 785

方法一: BFS + 染色

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # BFS
        from collections import deque
        n = len(graph)
        
        UNCOLORED, RED, GREEN = 0, 1, 2
        color = [UNCOLORED]*n  # 暂时标记为颜色0
        # 颜色: 0 代表未被涂色
        q = deque()
        q.append(0)
        color[0] = RED
        round_cnt = 0
        for i in range(n):
            if color[i] == UNCOLORED:
                q.append(i)
            while q:
                round_cnt +=1
                for _ in range(len(q)):
                    cur_node = q.popleft()
                    color_next = GREEN if color[cur_node] == RED else RED
                    for next_i in graph[cur_node]:
                        if color[next_i] == UNCOLORED:
                            color[next_i] = color_next
                            q.append(next_i)
                        elif color[next_i] != color_next:
                            return False  
        return True

方法二: DFS + 染色

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # DFS

        n = len(graph)
        UNCOLORED, RED, GREEN = 0, 1, 2
        color = [UNCOLORED]*n  # 暂时标记为颜色0
        # 颜色: 0 代表未被涂色
        res = True
        def dfs(x, color_cur):
            nonlocal res
            color[x] = color_cur
            color_next = GREEN if color[x] == RED else RED
            for next_i in graph[x]:
                if color[next_i] == UNCOLORED:
                    color[next_i] = color_next
                    dfs(next_i, color_next)
                    if res == False:
                        return
                elif color[next_i]!=color_next:
                    res =  False
                    return 
            #return True
        for i in range(n):
            if color[i] == UNCOLORED:
                dfs(i, RED)
                if res == False:
                    break
        return res

方法三:并查集

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.rank = [1]*n 
        self.cnt = n 
    def find(self, x):
        if x == self.root[x]:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x]>self.rank[root_y]:
                self.root[root_y] = root_x
            elif self.rank[root_y] >self.rank[root_x]:
                self.root[root_x] = root_y 
            else:
                self.root[root_y] = root_x
                self.rank[root_x]+=1
    def isConnected(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # 并查集
        n = len(graph)
        
        uf = UnionFind(n)
        for i in range(n):
            for next_i in graph[i]:
                if uf.isConnected(i, next_i):
                    return False
                uf.union(graph[i][0], next_i) # 注意这里用的是和next_i “同组”的第一个节点,不能用i, 即uf.union(i, next_i)是错误的
        return True

随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[BFS/DFS/拓扑排序 模板题Python代码]http://www.zyiz.net/tech/detail-228468.html

上一篇:leetcode 剑指 Offer 66. 构建乘积数组 python

下一篇:python实现货币转换

赞(0)
关注微信小程序
程序员编程王-随时随地学编程

扫描二维码或查找【程序员编程王】

可以随时随地学编程啦!

技术文章导航 更多>
扫一扫关注最新编程教程