무방향 그래프가 하나 있다고 가정하고 그래프가 이분법인지 여부를 확인해야 합니다. 그래프의 모든 모서리 {u,v}가 A의 노드 u와 B의 노드 v를 갖도록 그래프의 노드를 두 세트 A와 B로 나눌 수 있을 때 그래프가 이분법이라는 것을 알 수 있습니다.
따라서 입력이 다음과 같으면
그러면 출력은 True, [0,4]는 집합 A에 있고 [1,2,3]은 집합 B에 있으며 모든 모서리는 A에서 A 또는 B에서 B가 아니라 A에서 B 또는 B에서 A입니다. .
이 문제를 해결하기 위해 다음 단계를 따르겠습니다-
-
dfs() 함수를 정의합니다. 출처가 필요합니다
-
그래프[source]의 각 꼭짓점에 대해 수행
-
색상[정점]이 -1과 같지 않으면
-
색상[정점]이 색상[소스]와 같으면
-
결과[0] :=거짓
-
반환
-
-
다음 반복으로 이동
-
-
색상[정점] :=1 - 색상[소스]
-
dfs(정점)
-
-
기본 방법에서 다음을 수행하십시오-
-
n :=arr의 크기
-
graph :=정점 0에서 n-1에 대한 빈 인접 목록
-
0에서 n 사이의 i에 대해 수행
-
arr[i]의 각 j에 대해 수행
-
i를 그래프[j]에 삽입
-
그래프[i]에 j 삽입
-
-
color :=크기가 n인 목록과 -1로 채우기
-
result :=True 값이 하나인 목록
-
-
0에서 n 사이의 i에 대해 수행
-
color[i]가 -1과 같으면
-
dfs(i)
-
-
반환 결과[0]
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
from collections import defaultdict class Solution: def solve(self, arr): n = len(arr) graph = [set() for i in range(n)] for i in range(n): for j in arr[i]: graph[j].add(i) graph[i].add(j) color = [-1] * n result = [True] def dfs(source): for child in graph[source]: if color[child] != -1: if color[child] == color[source]: result[0] = False return continue color[child] = 1 - color[source] dfs(child) for i in range(n): if color[i] == -1: dfs(i) return result[0] ob = Solution() graph = [[1,2,3],[0],[0,4],[0,4],[2,3]] print(ob.solve(graph))
입력
graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]
출력
True