Lekcja – Problem 2 klik

```def is_bipartite(graph, clique1, clique2):

color = [-1] * len(graph)
current_node = 0
color[current_node] = 1

queue = []
queue.append(current_node)

while queue:

current_node = queue.pop()

if graph[current_node][current_node] == 1:
return False

for neighbour in range(len(graph)):
if graph[current_node][neighbour] == 1 and color[neighbour] == -1:
color[neighbour] = 1 - color[current_node]
queue.append(neighbour)
elif graph[current_node][neighbour] == 1 and color[neighbour] == color[current_node]:
return False

clique1.append([i for i in range(len(graph)) if color[i] == 0 or color[i] == -1])
clique2.append([i for i in range(len(graph)) if color[i] == 1 or color[i] == -1])
return True

def can_be_divided_2clique(graph, clique1, clique2):

complement_graph = [[None] * len(graph) for i in range(len(graph))]
for i in range(len(graph)):
for j in range(len(graph)):
complement_graph[i][j] = (graph[i][j]+1) % 2 if i != j else 0

return is_bipartite(complement_graph, clique1, clique2)

# graph = [
#     [0, 1, 1, 1, 0],
#     [1, 0, 1, 0, 0],
#     [1, 1, 0, 0, 0],
#     [0, 1, 0, 0, 1],
#     [0, 0, 0, 1, 0]
#     ]
#         D1 D2 P  K  Q  H
graph = [[0, 1, 1, 0, 0, 0],
[1, 0, 1, 0, 0, 0],
[1, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 1, 1],
[0, 0, 1, 1, 0, 1],
[0, 0, 1, 1, 1, 0]
]

clique1 = []
clique2 = []

if can_be_divided_2clique(graph, clique1, clique2):
print("Yes:")
print(clique1)
print(clique2)
else:
print("No")```

Lab

```g1 = [
[0,1,1,0,0,0,1,1],
[1,0,0,0,0,0,1,1],
[1,0,0,1,1,1,0,0],
[0,0,1,0,1,1,0,0],
[0,0,1,1,0,1,0,0],
[0,0,1,1,1,0,0,0],
[1,1,0,0,0,0,0,1],
[1,1,0,0,0,0,1,0]
]

g2 = [
[0,1,1,0,0,0,1,1],
[1,0,0,0,0,0,1,0],
[1,0,0,1,1,1,0,0],
[0,0,1,0,1,1,0,0],
[0,0,1,1,0,1,0,0],
[0,0,1,1,1,0,0,0],
[1,1,0,0,0,0,0,1],
[1,0,0,0,0,0,1,0]
]

def is_bipartite(graph, clique1, clique2):

color = [-1] * len(graph)
current_node = 0
color[current_node] = 1

queue = []
queue.append(current_node)

while queue:

current_node = queue.pop()

if graph[current_node][current_node] == 1:
return False

for neighbour in range(len(graph)):
if graph[current_node][neighbour] == 1 and color[neighbour] == -1:
color[neighbour] = 1 - color[current_node]
queue.append(neighbour)
elif graph[current_node][neighbour] == 1 and color[neighbour] == color[current_node]:
return False

clique1.append([i for i in range(len(graph)) if color[i] == 0 or color[i] == -1])
clique2.append([i for i in range(len(graph)) if color[i] == 1 or color[i] == -1])
return True

def can_be_divided_2clique(graph, clique1, clique2):

complement_graph = [[None] * len(graph) for i in range(len(graph))]
for i in range(len(graph)):
for j in range(len(graph)):
complement_graph[i][j] = (graph[i][j]+1) % 2 if i != j else 0

return is_bipartite(complement_graph, clique1, clique2)

clique1 = []
clique2 = []

if can_be_divided_2clique(g1, clique1, clique2):
print("Yes:")
print(clique1)
print(clique2)
else:
print("No")

clique1 = []
clique2 = []

if can_be_divided_2clique(g2, clique1, clique2):
print("Yes:")
print(clique1)
print(clique2)
else:
print("No")```