主題

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

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

題目:

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.
一個(gè)節(jié)點(diǎn)可以導(dǎo)向另外兩個(gè)不相連的節(jié)點(diǎn)，且其他的節(jié)點(diǎn)對其他的節(jié)點(diǎn)都一樣，則這些點(diǎn)可以標(biāo)記A和B來區(qū)隔開，最後可以完整的分完兩部分，那這個(gè)圖就是一個(gè)二分圖。

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)
            # 優(yōu)化list在頭尾進(jìn)行appened和pop等操作
            # 使得原本在list的時(shí)間複雜度是O(n)變成了O(1)
            # 利用append來初始化
            color[node] = 1

            while q:
                curr = q.popleft()
                # curr為q被移除的最左側(cè)元素
                for neighbor in graph[curr]:
                    if color[neighbor] == 0: #若未上1或-1則為前個(gè)節(jié)點(diǎn)的負(fù)數(shù)
                        color[neighbor] = -color[curr]
                        q.append(neighbor)
                    elif color[neighbor] == color[curr]:
                        # 若等於前一個(gè)節(jié)點(diǎn)則回傳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慢慢找慢慢塗

不過這題我花好久的時(shí)間才搞懂= =

怎麼感覺之前好像在C做過類似
collection 介紹