1from collections import deque
2class Vertex:
3 def __init__(self):
4 self.d = -1
5 self.edges = []
6
7class Solution:
8 def makingWiredConnections(self, graph):
9 for vertex in graph:
10 if not self.bfs(graph, vertex): return False
11 return True
12
13 def bfs(self, graph, vertex):
14 vertex.d = 0
15 queue = deque([vertex])
16 while queue:
17 node = queue.popleft()
18 for neighbour in node.edges:
19 if neighbour.d == node.d: return False
20 if neighbour.d == -1: neighbour.d = node.d + 1
21 return True