Bfs in Python, query

[dixith417]

Why this code does not update the ‘visited’ list???
I have also tried with global variables… did not work for me

[suman_18733097]

@dixith417

assume it is properly indented.

But it is difficult to understand dude. Paste your code in between a pair of 3 backticks(`). Or provide a link to the code. It would help grab the attention of readers.

[dixith417]

okay check again

[suman_18733097]

import sys
import collections
input = sys.stdin.readline
def bfs(v, visited, graph, q):
	q.append(v)
	visited[v] = True
	while not q:
		u = q.popleft()
		for e in graph[u]:
			if visited[e]:
				continue
			visited[e] = True
			q.append(e)

def magic(visited, graph, q):
	n, m = map(int, input().split())
	c = 0
	for i in range(m):
		u, v = map(int, input().split())
		u, v = u - 1, v - 1
		graph[u].append(v)
		graph[v].append(u)
	for i in range(n):
		print(visited[i])
		if not visited[i]:
			bfs(i, visited, graph, q)
			c += 1
	sys.stdout.write(str(c) + "\n")
	for i in range(n):
		sys.stdout.write(str(i) + ":" + str(graph[i]) + "\n")
	print("Visited List: ", visited[:10])

visited = [0 for _ in range(1000)]
graph = [[] for i in range(1000)]
q = collections.deque()
magic(visited, graph, q) 

@dixith417

Why this code does not update the ‘visited’ list???

It did

[suman_18733097]

I actually like the way you wrote your code. Readability is awesome. Keep going.

[dixith417]

Thanks! yes actually it did update ! but actually i was counting connected components in graph and it is giving wrong answer as ‘7’ bit it should be ‘2’ as per the graph. So, this was my confusion and thats why i thought it did not update the values.

see line 37 to 39 the value of c…

[suman_18733097]

This is extremely insane . I found the error.
Please remove the unnecessary print statements I put in the following code.
Error spotted at line 9.

import sys
import collections
input = sys.stdin.readline
def bfs(v, visited, graph, q):
	q.append(v)
	print("Visited: ", visited[:10])
	print("Queue", q)
	print(not q)
	while q: #The bug is here
		print("Queue", q)
		u = q.popleft()
		for e in graph[u]:
			if visited[e]:
				continue
			visited[e] = True
			q.append(e)

def magic(visited, graph, q):
	n, m = map(int, input().split())
	c = 0
	for i in range(m):
		u, v = map(int, input().split())
		u, v = u - 1, v - 1
		graph[u].append(v)
		graph[v].append(u)
	for i in range(n):
		print(visited[:10])
		if visited[i] == False:
			visited[i] = True
			bfs(i, visited, graph, q)
			c += 1
	sys.stdout.write(str(c) + "\n")
	for i in range(n):
		sys.stdout.write(str(i) + ":" + str(graph[i]) + "\n")
	print("Visited List: ", visited[:10])

visit = [False for _ in range(1000)]
graph = [[] for i in range(1000)]
q = collections.deque()
magic(visit, graph, q) 

And why didn’t we both check that line

[dixith417]

ohh!! "while q " since I was shifting a bit towards python from c++ I thought this is how to check if a queue is empty … solved it now Thanks