jan25's blog

Runtime error with Python3
By jan25, history, 6 years ago, In English

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)
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Most likely test 8 is the first test with an isolated vertex, which produces a KeyError because of the way you store the graph.

Here is a similar but smaller test demonstrating the error:

3 1
1 2

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The Key Error makes sense. Thanks!

    → Reply