숫자 n과 적이라는 2D 행렬이 있다고 가정합니다. 여기서 n은 [0, n - 1]에서 레이블이 지정된 n명의 사람들이 있음을 나타냅니다. 이제 적의 각 행에는 [a, b]가 포함되며, 이는 및 b가 적임을 의미합니다. 같은 그룹에 적이 되는 두 사람이 없도록 n명을 두 그룹으로 나누는 것이 가능한지 확인해야 합니다.
따라서 입력이 n =4, 적수 =[[0, 3],[3, 2]]인 경우 이 두 그룹 [0, 1, 2] 및 [ 3].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
그래프 :=빈 인접 목록
-
적의 각 적 쌍(u, v)에 대해 수행
-
그래프 끝에 v 삽입[u]
-
그래프 끝에 u 삽입[v]
-
-
색상 :=새 지도
-
dfs() 함수를 정의합니다. 처음에는 u, c :=0이 필요합니다.
-
u가 색상이면
-
color[u]가 c
와 같으면 true를 반환합니다.
-
-
색상[u] :=c
-
그래프[u]의 각 v에 대한 모든 dfs(v, c XOR 1)가 참일 때 참을 반환
-
주요 방법에서 다음을 수행하십시오 -
-
0에서 n 사이의 각 u에 대한 모든 (dfs(u) 및 u가 색상이 아닌 경우) 참일 때 참을 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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