-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdislike.py
153 lines (118 loc) · 3.72 KB
/
dislike.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
"""Create a function possible_bipartition which takes in an adjacency list representing a graph of puppies, dislikes.
The function should determine whether the puppies can be divided into two groups where no two puppies
that dislike each other are in the same group."""
from collections import deque
# dislikes = {
# "Fido": [],
# "Nala": ["Cooper", "Spot"],
# "Cooper": ["Nala", "Bruno"],
# "Spot": ["Nala"],
# "Bruno": ["Cooper"]
# }
dislikes = {
"Fido": [],
"Nala": ["Cooper", "Spot"],
"Cooper": ["Nala", "Spot"],
"Spot": ["Nala", "Cooper"]
}
# dislikes = {
# "Fido": [],
# "Rufus": [],
# "James": [],
# "Alfie": ["T-Bone"],
# "T-Bone": ["Alfie", "Scruffy"],
# "Scruffy": ["T-Bone"],
# "Bruno": ["Nala"],
# "Calico": ["Nala"],
# "Nala": ["Bruno", "Calico"]
# }
def possible_bipartition(dislikes):
unvisited= set(dislikes.keys())
blue =set()
red = set()
queue = deque()
while unvisited:
s= unvisited.pop()
red.add(s)
queue.append(s)
while queue:
curr= queue.popleft()
for n in dislikes[curr]:
if n not in blue and n not in red:
if curr in red:
blue.add(n)
else:
red.add(n)
else:
if ( n in blue and curr in blue ) or (n in red and curr in red):
return False
unvisited -=blue
unvisited -=red
return True
# red = set()
# blue =set()
# unvisited = set(dislikes.keys())
# while unvisited:
# S= unvisited.pop()
# red.add(S)
# queue = deque([S])
# while queue:
# curr = queue.popleft()
# for n in dislikes[curr]:
# if n not in red and n not in blue:
# if curr in red:
# blue.add(n)
# else:
# red.add(n)
# queue.append(n)
# else:
# if (curr in red and n in red) or (curr in blue and n in blue):
# return False
# unvisited -=blue
# unvisited -=red
# return True
# blue = set()
# red = set()
# unvisited = set(dislikes.keys())
# while unvisited:
# s = unvisited.pop()
# red.add(s)
# queue = deque([s])
# while queue:
# curr = queue.popleft()
# for n2 in dislikes[curr]:
# if n2 not in red and n2 not in blue:
# if curr in red:
# blue.add(n2)
# else:
# red.add(n2)
# queue.append(n2)
# else:
# if (curr in red and n2 in red) or (curr in blue and n2 in blue):
# return False
# unvisited -= blue
# unvisited -= red
# return True
print(possible_bipartition(dislikes))
# blue = set()
# red = set()
# unvisited = set(dislikes.keys())
# while unvisited:
# s = unvisited.pop()
# red.add(s)
# r = deque([s])
# while r:
# curr = r.popleft()
# for n2 in dislikes[curr]:
# if n2 not in red and n2 not in blue:
# if curr in red:
# blue.add(n2)
# else:
# red.add(n2)
# r.append(n2)
# else:
# if (curr in blue and n2 in blue) or (curr in red and n2 in red):
# return False
# unvisited -= red
# unvisited -= blue
# return True