題目:
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來區隔開，最後可以完整的分完兩部分，那這個圖就是一個二分圖。
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 介紹
collection 介紹
