Skip to content

Instantly share code, notes, and snippets.

@rpf5573
Created February 18, 2019 03:12
Show Gist options
  • Save rpf5573/ad99b009c991eec5beeb8a1d1b9339e1 to your computer and use it in GitHub Desktop.
Save rpf5573/ad99b009c991eec5beeb8a1d1b9339e1 to your computer and use it in GitHub Desktop.
from collections import deque
q = deque()
def bfs(index, computers):
q.append(index)
while not (len(q) == 0):
i = q.popleft()
computers[i][i] = 0
for z in range(len(computers[i])):
if computers[i][z] == 1:
q.append(z)
computers[i][z] = 0
computers[z][i] = 0
def solution(n, computers):
network_count = 0
for i in range(len(computers)):
if sum(computers[i]) > 0 :
bfs(i, computers)
network_count = network_count+1
return network_count
computers = [
[1,1,0],
[1,1,1],
[0,1,1]
]
print(solution(3, computers)) # 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment