Problem p03450 (python)

Fixed submission:
from collections import deque

def main():
    N, M = map(int, input().split())
    link = [[] for _ in range(N+1)]
    value = [0 for _ in range(N+1)]

    for _ in range(M):
        l, r, d = map(int, input().split())
        link[l].append((r, d))
        link[r].append((l, -d))

    searched = set()
    q = deque()
    for u in range(N+1):
        if u in searched:
            continue
        q.append(u)
        searched.add(u)
        value[u] = 0

        # search
        while q:
            x = q.popleft()
            for y, d in link[x]:
                if y not in searched:
                    value[y] = value[x] + d
                    q.append(y)
                    searched.add(y)

    # verify
    for x in range(N+1):
        for y, d in link[x]:
            if value[y] != value[x] + d:
                print('No')
                return
    else:
        print('Yes')

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
from collections import deque
N, M = map(int, input().split())
link = [[] for _ in range(N+1)]
value = [-1 for _ in range(N+1)]

for _ in range(M):
    l, r, d = map(int, input().split())
    G[l].append((r, d))
    G[r].append((l, -d))

searched = set()
q = deque()
for u in range(N+1):
    if u in searched:
        continue
    q.append(u)
    searched.add(u)
    value[u] = 0
    while q:
        x = q.popleft()
        for y, d in link[x]:
            if y not in searched:
                value[y] = value[x] + d
                q.append(y)
                searched.add(y)

for x in range(N+1):
    for y, d in link[x]:
        if value[y] != value[x] + d:
            print('No')
            break
else:
    print('Yes')

Buggy submission (verdict: Runtime Error):
from collections import deque
N, M = map(int, input().split())
link = [[] for _ in range(N+1)]
value = [-1 for _ in range(N+1)]

for _ in range(M):
    l, r, d = map(int, input().split())
    G[l].append((r, d))
    G[r].append((l, -d))

searched = set()
q = deque()
for u in range(N+1):
    if u in searched:
        continue
    q.append(u)
    searched.add(u)
    value[u] = 0
    while q:
        x = q.popleft()
        for y, v in link[x]:
            if y not in searched:
                value[y] = value[x] + d
                q.append(y)
                searched.add(y)

for x in range(N+1):
    for y, d in link[x]:
        if value[y] != value[x] + d:
            print('No')
            break
else:
    print('Yes')

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]

# weighted graph
for _ in range(M):
    l, r, d = map(int, input().split())
    G[l].append((r, d))
    G[r].append((l, -d))

cache = set(range(1, N+1))

# depth first search
def dfs(graph, start, visited=None):
    global cache  # for checking disconnected
    visited = visited or {}
    visited[start[0]] = start[1]
    cache.remove(start[0])
    for nxt, v in graph[start[0]]:
        nxt_value = start[1] + v
        if nxt in visited:
            if nxt_value != visited[nxt]:
                return False
            continue
        return dfs(graph, (nxt, nxt_value), visited)
    return True

# while len(cache)>0:
#     if not dfs(G, (list(cache)[0], 0)):
#         print('No')
#         break
# else:
#     print('Yes')

if dfs(G, (0, 0)):
    print('Yes')
else:
    print('No')

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]

# weighted graph
for _ in range(M):
    l, r, d = map(int, input().split())
    G[l].append((r, d))
    G[r].append((l, -d))

cache = set(range(1, N+1))

# depth first search
def dfs(graph, start, visited=None):
    global cache  # for checking disconnected
    visited = visited or {}
    visited[start[0]] = start[1]
    cache.remove(start[0])
    for nxt, v in graph[start[0]]:
        nxt_value = start[1] + v
        if nxt in visited:
            if nxt_value != visited[nxt]:
                return False
            continue
        return dfs(graph, (nxt, nxt_value), visited)
    return True

while len(cache)>0:
    if not dfs(G, (list(cache)[0], 0)):
        print('No')
        break
else:
    print('Yes')