Hi folks, I keep getting Runtime error with this implementation in Python3.6. Same implementation in C++11 is Accepted Pls comment if you find something off. Thanks! Here's the link to problem
n, m = map(int, input().split())
g = {v : [] for v in range(1, n + 1)}
for e in range(m):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
glob_vis = set()
def bfs(v):
vis = set([v])
glob_vis.add(v)
q = [v]
qi, e = 0, 0
while qi < len(q):
v = q[qi]
for u in g[v]:
e += 1
if u not in vis:
vis.add(u)
glob_vis.add(u)
q.append(u)
qi += 1
return [e//2, len(vis)]
min_sep = 0
for v in range(1, n + 1):
if v not in glob_vis:
res = bfs(v)
if res[0] == res[1] - 1:
min_sep += 1
print (min_sep)
Most likely test 8 is the first test with an isolated vertex, which produces a
KeyErrorbecause of the way you store the graph.Here is a similar but smaller test demonstrating the error:
Note that your submission has this problem, but the code in the question actually passes, which adds to the confusion.
Generally, I'd advice
g = [[] for v in range (n + 1)]instead of a dictionary, hoping that a plain list is more efficient as long as we know that vertices are numbered from 1 to n.The Key Error makes sense. Thanks!