Problem p02762 (python)

Fixed submission:
# -*- coding: utf-8 -*-

class UnionFindTree():
    def __init__(self, n):
        self.parent = []
        self.rank = []
        self.number = []
        for i in range(n):
            self.parent.append(i)
            self.rank.append(0)
            self.number.append(1)

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.number[y] += self.number[x]
        else:
            self.parent[y] = x
            self.number[x] += self.number[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def union_number(self, x):
        x = self.find(x)
        return self.number[x]

    def same_union_list(self, x):
        l = []
        for i in range(len(self.parent)):
            if i != x:
                if self.same(x, i):
                    l.append(i)
        
        return l

[N, M, K] = [int(i) for i in input().split()]

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

CD = []
for k in range(K):
    [c, d] = [int(i) for i in input().split()]
    CD.append((c, d))

uf_tree = UnionFindTree(N)
for (a, b) in AB:
    a -= 1
    b -= 1
    uf_tree.unite(a, b)

candidates = []
for n in range(N):
    candidates.append(uf_tree.union_number(n) - 1)

for (a, b) in AB:
    a -= 1
    b -= 1
    candidates[a] -= 1
    candidates[b] -= 1

for (c, d) in CD:
    c -= 1
    d -= 1
    if uf_tree.same(c, d):
        candidates[c] -= 1
        candidates[d] -= 1

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

print(ans[:len(ans) - 1])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

class UnionFindTree():
    def __init__(self, n):
        self.parent = []
        self.rank = []
        for i in range(n):
            self.parent.append(i)
            self.rank.append(0)

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def same_union_list(self, x):
        l = []
        for i in range(len(self.parent)):
            if i != x:
                if self.same(x, i):
                    l.append(i)
        
        return l

[N, M, K] = [int(i) for i in input().split()]

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

CD = []
for k in range(K):
    [c, d] = [int(i) for i in input().split()]
    CD.append((c, d))

uf_tree = UnionFindTree(N)
friends = {}
blocks = {}

for (a, b) in AB:
    a -= 1
    b -= 1
    if a not in friends:
        friends[a] = []
    if b not in friends:
        friends[b] = []
    friends[a].append(b)
    friends[b].append(a)
    uf_tree.unite(a, b)

candidates = []
#print(uf_tree.parent)
#print(uf_tree.rank)
#print(friends)
#print(blocks)
for n in range(N):
    same_union_list = uf_tree.same_union_list(n)
    #print('{}\'s union_list: {}'.format(n, same_union_list))
    candidates.append(len(same_union_list) - len(friends[n]))

for (c, d) in CD:
    c -= 1
    d -= 1
    if uf_tree.same(c, d):
        candidates[c] -= 1
        candidates[d] -= 1

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

print(ans[:len(ans) - 1])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

class UnionFindTree():
    def __init__(self, n):
        self.parent = []
        self.rank = []
        for i in range(n):
            self.parent.append(i)
            self.rank.append(0)

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def same_union_list(self, x):
        l = []
        for i in range(len(self.parent)):
            if i != x:
                if self.same(x, i):
                    l.append(i)
        
        return l

[N, M, K] = [int(i) for i in input().split()]

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

CD = []
for k in range(K):
    [c, d] = [int(i) for i in input().split()]
    CD.append((c, d))

uf_tree = UnionFindTree(N)
friends = {}
blocks = {}

for (a, b) in AB:
    a -= 1
    b -= 1
    if a not in friends:
        friends[a] = []
    if b not in friends:
        friends[b] = []
    friends[a].append(b)
    friends[b].append(a)
    uf_tree.unite(a, b)

for (c, d) in CD:
    c -= 1
    d -= 1
    if c not in blocks:
        blocks[c] = []
    if d not in blocks:
        blocks[d] = []
    blocks[c].append(d)
    blocks[d].append(c)

candidates = []
#print(uf_tree.parent)
#print(uf_tree.rank)
#print(friends)
#print(blocks)
for n in range(N):
    same_union_list = uf_tree.same_union_list(n)
    #print('{}\'s union_list: {}'.format(n, same_union_list))
    if n in blocks:
        for b in blocks[n]:
            if b in same_union_list:
                same_union_list.remove(b)
    candidates.append(len(same_union_list) - len(friends[n]))

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

print(ans[:len(ans) - 1])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

def display(node):
        print('----')
        print('val: {}'.format(node.val))
        print('friend_numbers: {}'.format(node.friend_numbers))
        print('block_numbers: {}'.format(node.block_numbers))
        print('candidate_numbers: {}'.format(node.candidate_numbers))

#def find_friend(root, target):
#    queue = [root]
#    already_list = [root.val]
#    while len(queue) > 0:
#        node = queue.pop(0)
#        if target in node.friend_numbers:
#            return True
#        if target in node.candidate_numbers:
#            return True
#        
#        for friend in node.friends:
#            if friend.val not in already_list:
#                queue.append(friend)
#                already_list.append(friend.val)

def find_friend(tree_node, target, already_list):
    for friend in tree_node.friends:
        if target in friend.friend_numbers:
            return True
        if target in friend.candidate_numbers:
            return True

    flags = []
    for friend in tree_node.friends:
        if friend.val not in already_list:
            new_already_list = already_list[:]
            new_already_list.append(friend.val)
            flags.append(find_friend(friend, target, new_already_list))
    if True in flags:
        return True
    return False


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.friends = []
        self.friend_numbers = []
        self.blocks = []
        self.block_numbers = []
        self.candidate_numbers = []

[N, M, K] = [int(i) for i in input().split()]

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

CD = []
for k in range(K):
    [c, d] = [int(i) for i in input().split()]
    CD.append((c, d))

tree_nodes = {}
for i in range(1, N + 1):
    tree_node = TreeNode(i)
    tree_nodes[i] = tree_node

for (a, b) in AB:
    tree_nodes[a].friends.append(tree_nodes[b])
    tree_nodes[a].friend_numbers.append(b)
    tree_nodes[b].friends.append(tree_nodes[a])
    tree_nodes[b].friend_numbers.append(a)

for (c, d) in CD:
    tree_nodes[c].blocks.append(tree_nodes[d])
    tree_nodes[c].block_numbers.append(d)
    tree_nodes[d].blocks.append(tree_nodes[c])
    tree_nodes[d].block_numbers.append(c)

candidates = []
for k, v in tree_nodes.items():
    # 友達候補を探す
    candidate = 0
    for n in range(1, N + 1):
        if n == k:
            continue
        if n in v.friend_numbers:
            continue
        if n in v.block_numbers:
            continue

        flag = False
        # nさんが既に自分を友達候補にしていればOK
        if k in tree_nodes[n].candidate_numbers:
            flag = True
        else:
            # nさんへの友達経路があるか探索
            flag = find_friend(v, n, [v.val])
        if flag:
            candidate += 1
            v.candidate_numbers.append(n)
        #print('{}の友達候補{}: {}'.format(k, n, flag))
    
    candidates.append(candidate)

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

#for k, v in tree_nodes.items():
#    display(v)

print(ans[:len(ans) - 1])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

def display(node):
        print('----')
        print('val: {}'.format(node.val))
        print('friend_numbers: {}'.format(node.friend_numbers))
        print('block_numbers: {}'.format(node.block_numbers))
        print('candidate_numbers: {}'.format(node.candidate_numbers))

#def find_friend(root, target):
#    queue = [root]
#    already_list = [root.val]
#    while len(queue) > 0:
#        node = queue.pop(0)
#        if target in node.friend_numbers:
#            return True
#        if target in node.candidate_numbers:
#            return True
#        
#        for friend in node.friends:
#            if friend.val not in already_list:
#                queue.append(friend)
#                already_list.append(friend.val)

def find_friend(tree_node, target):
    for friend in tree_node.friends:
        if target in friend.friend_numbers:
            return True
        if target in friend.candidate_numbers:
            return True

    flags = []
    for friend in tree_node.friends:
        flags.append(find_friend(friend, target))
    if True in flags:
        return True
    return False


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.friends = []
        self.friend_numbers = []
        self.blocks = []
        self.block_numbers = []
        self.candidate_numbers = []

[N, M, K] = [int(i) for i in input().split()]

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

CD = []
for k in range(K):
    [c, d] = [int(i) for i in input().split()]
    CD.append((c, d))

tree_nodes = {}
for i in range(1, N + 1):
    tree_node = TreeNode(i)
    tree_nodes[i] = tree_node

for (a, b) in AB:
    tree_nodes[a].friends.append(tree_nodes[b])
    tree_nodes[a].friend_numbers.append(b)
    tree_nodes[b].friends.append(tree_nodes[a])
    tree_nodes[b].friend_numbers.append(a)

for (c, d) in CD:
    tree_nodes[c].blocks.append(tree_nodes[d])
    tree_nodes[c].block_numbers.append(d)
    tree_nodes[d].blocks.append(tree_nodes[c])
    tree_nodes[d].block_numbers.append(c)

candidates = []
for k, v in tree_nodes.items():
    # 友達候補を探す
    candidate = 0
    for n in range(1, N + 1):
        if n == k:
            continue
        if n in v.friend_numbers:
            continue
        if n in v.block_numbers:
            continue

        flag = False
        # nさんが既に自分を友達候補にしていればOK
        if k in tree_nodes[n].candidate_numbers:
            flag = True
        else:
            # nさんへの友達経路があるか探索
            flag = find_friend(v, n)
        if flag:
            candidate += 1
            v.candidate_numbers.append(n)
        #print('{}の友達候補{}: {}'.format(k, n, flag))
    
    candidates.append(candidate)

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

#for k, v in tree_nodes.items():
#    display(v)

print(ans[:len(ans) - 1])