資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：將人員分組，確保無敵人處於同一組
假設我們有一個數字n和一個名為enemies的二維矩陣。這裡n表示有n個人，編號從[0, n - 1]。現在enemies中的每一行都包含[a, b]，這意味著a和b是敵人。我們必須檢查是否可以將n個人分成兩組，使得沒有任何兩個敵人處於同一組。
因此，如果輸入類似於n = 4，enemies = [[0, 3],[3, 2]]，則輸出為True，因為我們可以有這兩組[0, 1, 2]和[3]。
為了解決這個問題，我們將遵循以下步驟：
graph := 一個空的鄰接表
對於enemies中的每個敵人對(u, v)，執行以下操作：
將v插入graph[u]的末尾
將u插入graph[v]的末尾
color := 一個新的對映
定義一個函式dfs()。它將接收u，c := 最初為0
如果u在color中，則
當color[u]與c相同時返回true
color[u] := c
當graph[u]中每個v的dfs(v, c XOR 1)都為true時返回true
從主方法執行以下操作：
當(從0到n的每個u，如果u不在color中，則dfs(u))都為true時返回true
讓我們看看下面的實現，以便更好地理解：
示例
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))輸入
4, [[0, 3],[3, 2]]
輸出
True
更新於：2020年10月21日
522 次瀏覽
廣告