กราฟไม่มีทิศทาง ตรวจสอบว่าเป็น bipartite ได้ไหม (แบ่งโหนดเป็น 2 เซต ทุกเส้นเชื่อมข้ามเซต)
ตัวอย่าง: กราฟ [[1,2,3],[0],[0,4],[0,4],[2,3]] → True (เซต A: 0,4; เซต B: 1,2,3)
อัลกอริธึม DFS Coloring
- สร้าง adjacency list
- อาร์เรย์
color: -1=ยังไม่ระบาย, 0/1=สี - DFS จากทุกโหนดที่ยังไม่มีสี: ระบายลูกด้วยสีตรงข้าม ถ้าพบลูกสีเดียวกัน → ไม่ใช่ bipartite
การนำไปใช้
from collections import defaultdict
class Solution:
def solve(self, arr):
n = len(arr)
graph = [set() for _ 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()
print(ob.solve([[1,2,3],[0],[0,4],[0,4],[2,3]])) # True
