Problem p02762 (python)

Fixed submission:
import sys
sys.setrecursionlimit(4100000)

from collections import Counter

N, M, K = map(int, input().split())

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return 0

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        if graph_g[edge] == None:
            dfs(edge, graph_cnt)


for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)

for i in range(N):
    if is_visited[i]:
        continue
    dfs(i, None)

for i in range(K):
    C, D = map(int, input().split())
    if graph_g[C-1] == graph_g[D-1]:
        block[C-1].append(D-1)
        block[D-1].append(C-1)

ct = Counter(graph_g)

ret = []
for i in range(N):
    cand = ct[graph_g[i]]
    fri = len(to[i])
    tmp_block = len(block[i])

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(4100000)

N, M, K = map(int, input().split())

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)

for i in range(K):
    C, D = map(int, input().split())
    block[C-1].append(D-1)
    block[D-1].append(C-1)

for i in range(N):
    if is_visted[i]:
        continue
    dfs(i, None)

group_to_idx = [set() for i in range(graph_cnt+1)]
if len(group_to_idx) != 0:
    for i in range(N):
        group_to_idx[graph_g[i]].add(i)

ret = []
for i in range(N):
    cand = len(group_to_idx[graph_g[i]])
    fri = len(to[i])
    tmp_block = len(group_to_idx[graph_g[i]] & set(block[i]))

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Buggy submission (verdict: Runtime Error):
N, M, K = map(int, input().split())

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)

for i in range(K):
    C, D = map(int, input().split())
    block[C-1].append(D-1)
    block[D-1].append(C-1)

for i in range(N):
    dfs(i, None)

group_to_idx = [set() for i in range(graph_cnt+1)]
if len(group_to_idx) != 0:
    for i in range(N):
        group_to_idx[graph_g[i]].add(i)

ret = []
for i in range(N):
    cand = len(group_to_idx[graph_g[i]])
    fri = len(to[i])
    tmp_block = len(group_to_idx[graph_g[i]] & set(block[i]))

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Buggy submission (verdict: Runtime Error):
N, M, K = map(int, input().split())

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)

for i in range(K):
    C, D = map(int, input().split())
    block[C-1].append(D-1)
    block[D-1].append(C-1)

for i in range(N):
    dfs(i, None)

group_to_idx = [set() for i in range(graph_cnt+1)]
for i in range(N):
    group_to_idx[graph_g[i]].add(i)

ret = []
for i in range(N):
    cand = len(group_to_idx[graph_g[i]])
    fri = len(to[i])
    tmp_block = len(group_to_idx[graph_g[i]] & set(block[i]))

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Buggy submission (verdict: Runtime Error):
N, M, K = map(int, input().split())

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)

for i in range(K):
    C, D = map(int, input().split())
    block[C-1].append(D-1)
    block[D-1].append(C-1)

for i in range(N):
    dfs(i, None)

group_to_idx = [set() for i in range(graph_cnt+1)]
for i in range(N):
    group_to_idx[graph_g[i]].add(i)

ret = []
for i in range(N):
    cand = len(group_to_idx[graph_g[i]])
    fri = len(to[i])
    tmp_block = len(group_to_idx[graph_g[i]] & set(block[i]))

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Buggy submission (verdict: Runtime Error):
N, M, K = map(int, input().split())

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)
    flg = False
    A_idx = None
    B_idx = None
    for tmp_idx, tmp_set in enumerate(sets):
        if A - 1 in tmp_set:
            A_idx = tmp_idx
        if B - 1 in tmp_set:
            B_idx = tmp_idx
        if A - 1 in tmp_set or B - 1 in tmp_set:
            flg = True
            tmp_set.add(A - 1)
            tmp_set.add(B - 1)

    if not flg:
        sets.append({A-1, B-1})
    elif A_idx != None and B_idx != None and A_idx != B_idx:
        for j in sets[B_idx]:
            sets[A_idx].add(j)
        sets.pop(B_idx)

for i in range(K):
    C, D = map(int, input().split())
    block[C-1].append(D-1)
    block[D-1].append(C-1)

for i in range(N):
    i_idx = -1
    for tmp_idx, tmp_set in enumerate(sets):
        if i in tmp_set:
            i_idx = tmp_idx
    l = len(sets[i_idx])
    m1 = len(to[i])
    
    m2 = 0
    for j in block[i]:
        if j in sets[i_idx]:
            m2 += 1

    if i != N-1:
        print(l - 1 - m1 - m2, end=' ')
    else:
        print(l - 1 - m1 - m2)

Buggy submission (verdict: Runtime Error):
N, M, K = map(int, input().split())

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)
    flg = False
    A_idx = None
    B_idx = None
    for tmp_idx, tmp_set in enumerate(sets):
        if A - 1 in tmp_set:
            A_idx = tmp_idx
        if B - 1 in tmp_set:
            B_idx = tmp_idx
        if A - 1 in tmp_set or B - 1 in tmp_set:
            flg = True
            tmp_set.add(A - 1)
            tmp_set.add(B - 1)

    if not flg:
        sets.append({A-1, B-1})
    elif A_idx != None and B_idx != None and A_idx != B_idx:
        for j in sets[B_idx]:
            sets[A_idx].add(j)
        sets.pop(B_idx)

for i in range(K):
    C, D = map(int, input().split())
    block[C-1].append(D-1)
    block[D-1].append(C-1)

print(sets)

for i in range(N):
    i_idx = -1
    for tmp_idx, tmp_set in enumerate(sets):
        if i in tmp_set:
            i_idx = tmp_idx
    l = len(sets[i_idx])
    m1 = len(to[i])
    
    m2 = 0
    for j in block[i]:
        if j in sets[i_idx]:
            m2 += 1

    if i != N-1:
        print(l - 1 - m1 - m2, end=' ')
    else:
        print(l - 1 - m1 - m2)