Problem p02762 (python)

Fixed submission:
"""
D-Friend Suggestions
BFS
"""

import sys
input = sys.stdin.readline
from collections import deque, Counter


def main():
    N, M, K = map(int, input().split())
    friend = [[] for _ in range(N)]
    block = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        friend[a - 1].append(b - 1)
        friend[b - 1].append(a - 1)

    for _ in range(K):
        c, d = map(int, input().split())
        block[c - 1].append(d - 1)
        block[d - 1].append(c - 1)

    label_list = [-1] * N
    label = 0
    for start_vertex in range(N):
        q = deque()

        def push(vertex, label):
            if label_list[vertex] != -1:
                return
            q.append(vertex)
            label_list[vertex] = label

        push(start_vertex, label)

        while len(q) != 0:
            vertex = q.popleft()
            friend_vertexes = friend[vertex]
            for f_vertex in friend_vertexes:
                push(f_vertex, label)
        label += 1

    connected_component_id = Counter(label_list)

    ans = []
    for i in range(N):
        vertex_label = label_list[i]
        connected_qty = connected_component_id[vertex_label]

        for j in block[i]:
            if label_list[i] == label_list[j]:
                connected_qty -= 1

        ans.append(connected_qty - len(friend[i]) - 1)

    print(*ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
"""
Friend Suggestions
"""

import sys
input = lambda: sys.stdin.readline().rstrip()


class Vertex:
    """A Vertex is a node in a graph."""
    def __init__(self, label=''):
        self.label = label

    def __repr__(self):
        return f'V{self.label}'

    __str__ = __repr__


class Edge(tuple):
    """An Edge is a list of two vertices."""
    def __new__(cls, *vs):
        """The Edge constructor takes two vertices."""
        if len(vs) != 2:
            raise ValueError("Edges must connect exactly two vertices.")
        return tuple.__new__(cls, vs)

    def __repr__(self):
        return f'Edge_{repr(self[0])}_{repr(self[1])}'

    __str__ = __repr__


class Graph(dict):
    """A Graph is a dictionary of dictionaries.
    For vertices a and b, graph[a][b] maps
    to the edge that connects a->b, if it exists."""

    def __init__(self, vs, es):
        """Creates a new graph.
        vs: list of vertices;
        es: list of edges.
        """
        super().__init__()
        for v in vs:
            self.add_vertex(v)
        for e in es:
            self.add_edge(e)

    def add_vertex(self, v):
        """Add a vertex to the graph."""
        self[v] = {}

    def add_edge(self, e):
        """Adds and edge to the graph by adding an entry in both directions."""
        v, w = e
        self[v][w] = e
        self[w][v] = e

    def vertices(self):
        """returns a list of the vertices in graph"""
        vs = []
        for v in self.keys():
            vs.append(v)
        return vs

    def out_vertices(self, v):
        """returns a list of adjacent vertices of the (v)"""
        return self[v].keys()

    def out_edges(self, v):
        """returns a list of edges connected to the (v)"""
        return self[v].values()

    def is_connected(self):
        """returns True if the Graph is conneted and False otherwise"""
        vertices = self.vertices()
        closed = self.BFS(vertices[0])
        return len(vertices) == len(closed)

    def closed_vertices(self, v):
        return self.BFS(v)

    def BFS(self, v):
        """search graph by a BFS: breadth-first-search"""
        worklist = [v]
        closed = []
        while worklist:
            visited = worklist.pop(0)
            closed.append(visited)
            vs = self.out_vertices(visited)
            vs = [v for v in vs if not (v in closed or v in worklist)]
            worklist.extend(vs)
        return closed


def main():
    N, M, K = map(int, input().split())
    ans = [-1] * N

    friend = [list(map(int, input().split())) for _ in range(M)]
    blocks = [list(map(int, input().split())) for _ in range(K)]

    nodes = [Vertex(str(v)) for v in range(N)]
    edges = [Edge(nodes[edge[0]-1], nodes[edge[1]-1]) for edge in friend]
    g = Graph(nodes, edges)

    for i, v in enumerate(nodes):
        closed_graph_list = [str(x) for x in g.closed_vertices(v)]
        closed_graph_list.remove(str(v))
        connected_vertices = [str(x) for x in list(g.out_vertices(v))]
        candidates = list(set(closed_graph_list) - set(connected_vertices))
        ans[i] = candidates

    for block_rel in blocks:
        block_a = block_rel[0] - 1
        block_b = block_rel[1] - 1
        if f'V{block_b}' in ans[block_a]:
            ans[block_a].remove(f'V{block_b}')
        if f'V{block_a}' in ans[block_b]:
            ans[block_b].remove(f'V{block_a}')

    print(*[len(i) for i in ans])


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
class Vertex:
    """A Vertex is a node in a graph."""
    def __init__(self, label=''):
        self.label = label

    def __repr__(self):
        return f'V{self.label}'

    __str__ = __repr__


class Edge(tuple):
    """An Edge is a list of two vertices."""
    def __new__(cls, *vs):
        """The Edge constructor takes two vertices."""
        if len(vs) != 2:
            raise ValueError("Edges must connect exactly two vertices.")
        return tuple.__new__(cls, vs)

    def __repr__(self):
        return f'Edge_{repr(self[0])}_{repr(self[1])}'

    __str__ = __repr__


class Graph(dict):
    """A Graph is a dictionary of dictionaries.
    For vertices a and b, graph[a][b] maps
    to the edge that connects a->b, if it exists."""

    def __init__(self, vs, es):
        """Creates a new graph.
        vs: list of vertices;
        es: list of edges.
        """
        super().__init__()
        for v in vs:
            self.add_vertex(v)
        for e in es:
            self.add_edge(e)

    def add_vertex(self, v):
        """Add a vertex to the graph."""
        self[v] = {}

    def add_edge(self, e):
        """Adds and edge to the graph by adding an entry in both directions."""
        v, w = e
        self[v][w] = e
        self[w][v] = e

    def vertices(self):
        """returns a list of the vertices in graph"""
        vs = []
        for v in self.keys():
            vs.append(v)
        return vs

    def out_vertices(self, v):
        """returns a list of adjacent vertices of the (v)"""
        return self[v].keys()

    def out_edges(self, v):
        """returns a list of edges connected to the (v)"""
        return self[v].values()

    def is_connected(self):
        """returns True if the Graph is conneted and False otherwise"""
        vertices = self.vertices()
        closed = self.BFS(vertices[0])
        return len(vertices) == len(closed)

    def closed_vertices(self, v):
        return self.BFS(v)

    def BFS(self, v):
        """search graph by a BFS: breadth-first-search"""
        worklist = [v]
        closed = []
        while worklist:
            visited = worklist.pop(0)
            closed.append(visited)
            vs = self.out_vertices(visited)
            vs = [v for v in vs if not (v in closed or v in worklist)]
            worklist.extend(vs)
        return closed


def main():
    N, M, K = map(int, input().split())
    ans = [-1] * N

    friend = [list(map(int, input().split())) for _ in range(M)]
    blocks = [list(map(int, input().split())) for _ in range(K)]

    nodes = [Vertex(str(v)) for v in range(N)]
    edges = [Edge(nodes[edge[0]-1], nodes[edge[1]-1]) for edge in friend]
    g = Graph(nodes, edges)

    for i, v in enumerate(nodes):
        closed_graph_list = [str(x) for x in g.closed_vertices(v)]
        closed_graph_list.remove(str(v))
        connected_vertices = [str(x) for x in list(g.out_vertices(v))]
        candidates = list(set(closed_graph_list) - set(connected_vertices))
        ans[i] = candidates

    for block_rel in blocks:
        block_a = block_rel[0] - 1
        block_b = block_rel[1] - 1
        if f'V{block_b}' in ans[block_a]:
            ans[block_a].remove(f'V{block_b}')
        if f'V{block_a}' in ans[block_b]:
            ans[block_b].remove(f'V{block_a}')

    print(*[len(i) for i in ans])


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
"""
Friend Suggestions
"""

import sys
input = lambda: sys.stdin.readline().rstrip()


class Vertex:
    """A Vertex is a node in a graph."""
    def __init__(self, label=''):
        self.label = label

    def __repr__(self):
        return f'V{self.label}'

    __str__ = __repr__


class Edge(tuple):
    """An Edge is a list of two vertices."""
    def __new__(cls, *vs):
        """The Edge constructor takes two vertices."""
        if len(vs) != 2:
            raise ValueError("Edges must connect exactly two vertices.")
        return tuple.__new__(cls, vs)

    def __repr__(self):
        return f'Edge_{repr(self[0])}_{repr(self[1])}'

    __str__ = __repr__


class Graph(dict):
    """A Graph is a dictionary of dictionaries.
    For vertices a and b, graph[a][b] maps
    to the edge that connects a->b, if it exists."""

    def __init__(self, vs, es):
        """Creates a new graph.
        vs: list of vertices;
        es: list of edges.
        """
        super().__init__()
        for v in vs:
            self.add_vertex(v)
        for e in es:
            self.add_edge(e)

    def add_vertex(self, v):
        """Add a vertex to the graph."""
        self[v] = {}

    def add_edge(self, e):
        """Adds and edge to the graph by adding an entry in both directions."""
        v, w = e
        self[v][w] = e
        self[w][v] = e

    def vertices(self):
        """returns a list of the vertices in graph"""
        vs = []
        for v in self.keys():
            vs.append(v)
        return vs

    def out_vertices(self, v):
        """returns a list of adjacent vertices of the (v)"""
        return self[v].keys()

    def out_edges(self, v):
        """returns a list of edges connected to the (v)"""
        return self[v].values()

    def is_connected(self):
        """returns True if the Graph is conneted and False otherwise"""
        vertices = self.vertices()
        closed = self.BFS(vertices[0])
        return len(vertices) == len(closed)

    def closed_vertices(self, v):
        return self.BFS(v)

    def BFS(self, v):
        """search graph by a BFS: breadth-first-search"""
        worklist = [v]
        closed = []
        while worklist:
            visited = worklist.pop(0)
            closed.append(visited)
            vs = self.out_vertices(visited)
            vs = [v for v in vs if not (v in closed or v in worklist)]
            worklist.extend(vs)
        return closed


def main():
    N, M, K = map(int, input().split())
    ans = [-1] * N

    friend = [list(map(int, input().split())) for _ in range(M)]
    blocks = [list(map(int, input().split())) for _ in range(K)]

    nodes = [Vertex(str(v)) for v in range(N)]
    edges = [Edge(nodes[edge[0]-1], nodes[edge[1]-1]) for edge in friend]
    g = Graph(nodes, edges)

    for i, v in enumerate(nodes):
        closed_graph_list = [str(x) for x in g.closed_vertices(v)]
        closed_graph_list.remove(str(v))
        connected_vertices = [str(x) for x in list(g.out_vertices(v))]
        candidates = list(set(closed_graph_list) - set(connected_vertices))
        ans[i] = candidates

    for block_rel in blocks:
        block_a = block_rel[0] - 1
        block_b = block_rel[1] - 1
        if f'V{block_b}' in ans[block_a]:
            ans[block_a].remove(f'V{block_b}')
        if f'V{block_a}' in ans[block_b]:
            ans[block_b].remove(f'V{block_a}')

    print(*[len(i) for i in ans])


if __name__ == '__main__':
    main()