Giả sử chúng ta có một số n và một ma trận 2D được gọi là kẻ thù. Ở đây n cho biết có n người được gắn nhãn từ [0, n - 1]. Bây giờ mỗi hàng trong kẻ thù chứa [a, b] có nghĩa là a và b là kẻ thù. Chúng ta phải kiểm tra xem có thể phân chia n người thành hai nhóm sao cho không có hai người là kẻ thù trong cùng một nhóm hay không.
Vì vậy, nếu đầu vào giống như n =4, địch =[[0, 3], [3, 2]], thì đầu ra sẽ là Đúng, vì chúng ta có thể có hai nhóm này [0, 1, 2] và [ 3].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
graph:=một danh sách gần kề trống
-
đối với mỗi cặp kẻ thù (u, v) trong kẻ thù, thực hiện
-
chèn v vào cuối biểu đồ [u]
-
chèn u vào cuối biểu đồ [v]
-
-
color:=a new map
-
Định nghĩa một hàm dfs (). Điều này sẽ mất u, c:=0 ban đầu
-
nếu bạn có màu sắc, thì
-
trả về true khi màu [u] giống với c
-
-
color [u]:=c
-
trả về true khi tất cả các dfs (v, c XOR 1) cho mỗi v trong biểu đồ [u] đều đúng
-
Từ phương thức chính, hãy làm như sau -
-
trả về true khi tất cả (dfs (u) cho mỗi u trong phạm vi từ 0 đến n và nếu u không có màu) đều đúng
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution:
def solve(self, n, enemies):
from collections import defaultdict
graph = defaultdict(list)
for u, v in enemies:
graph[u].append(v)
graph[v].append(u)
color = {}
def dfs(u, c=0):
if u in color:
return color[u] == c
color[u] = c
return all(dfs(v, c ^ 1) for v in graph[u])
return all(dfs(u) for u in range(n) if u not in color)
ob = Solution()
n = 4
enemies = [[0, 3],[3, 2]]
print(ob.solve(n, enemies)) Đầu vào
4, [[0, 3],[3, 2]]
Đầu ra
True