ETH官方钱包

切換
舊版
前往
大廳
主題

[LeetCode] 785.Is Graph Bipartite? 很難欸= =新東西

テリ君(桃夫模式) | 2023-05-19 16:11:03 | 巴幣 4 | 人氣 292

題目:
There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

1.There are no self-edges (graph[u] does not contain u).
2.There are no parallel edges (graph[u] does not contain duplicate values).
3.If v is in graph[u], then u is in graph[v] (the graph is undirected).
4.The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite(二分的) if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.
一個節點可以導向另外兩個不相連的節點,且其他的節點對其他的節點都一樣,則這些點可以標記A和B來區隔開,最後可以完整的分完兩部分,那這個圖就是一個二分圖。

Return true if and only if it is bipartite.




from collections import deque

# using BFS
class Solution:
    def isBipartite(self, graph):
        n = len(graph)
        color = [0] * n
        for node in range(n):
            if color[node] != 0:
                continue

            q = deque([node])
            # deque(iterable[,maxlen])雙端佇列 (double-ended queue)
            # 優化list在頭尾進行appened和pop等操作

            # 使得原本在list的時間複雜度是O(n)變成了O(1)
            # 利用append來初始化
            color[node] = 1

            while q:
                curr = q.popleft()
                # curr為q被移除的最左側元素
                for neighbor in graph[curr]:
                    if color[neighbor] == 0: #若未上1或-1則為前個節點的負數
                        color[neighbor] = -color[curr]
                        q.append(neighbor)
                    elif color[neighbor] == color[curr]:
                        # 若等於前一個節點則回傳False
                        return False
        # 全部上完1 or -1則回傳True
        return True

sol = Solution()
print(sol.isBipartite([[1,3],[0,2],[1,3],[0,2]]))
print(sol.isBipartite([[1,2,3],[0,2],[0,1,3],[0,2]]))

//OUT PUT
True
False     

基本上就是用BFS慢慢找慢慢塗
不過這題我花好久的時間才搞懂= =
怎麼感覺之前好像在C做過類似
collection 介紹

創作回應

永遠18歲的永恆等待
竟然在刷題了 厲害喔
2023-05-24 02:45:56
テリ君(桃夫模式)
感謝啊柴學長,剛起步繼續努力
2023-05-24 10:37:32

更多創作