ABC288 回想・解説(Python)

Thumbnail

目次

前提

AtCoder Biginner Contest288のPythonの解答コードです。

A - Many A+B Problems

問題文通りに実装する。

N = int(input())
ans = []
for _ in range(N):
    a, b = map(int, input().split())
    ans.append(a + b)

for a in ans:
    print(a)

B - Qualification Contest

上位K人までをソートして出力する。

N, K = map(int, input().split())
S = [input() for _ in range(N)]

for s in sorted(S[:K]):
    print(s)

C -Don’t be cycle

UnionFindで閉路を検出する。検出したらカウントアップし、最後にカウントを出力する。

同じ親をもつノード同士を接続すると閉路になる。ちなみに同じ親ノードを持つかどうかを判定するsame関数を用意しているのにも関わらず、ついfind同士で比較してしまう、、

class UnionFind:
    """Union Find木クラス
    Attributes:
        parent (list): 親要素を格納するリスト。親要素は自身のサイズを格納する。
    Notes:
        - parent[i] < 0 の場合、iは根。この時、-parent[i]はそのグループのサイズ
        - parent[i] = -1 とすると、iは独立。
    """

    def __init__(self, n):
        """
        Args:
            n (int): The number of objects. 要素数
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """returns the root of x

        Args:
            x (int): The object to find the root of. 要素

        Returns:
            int: The root of x.
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """unites the root of x and the root of y

        Args:
            x (int): The first object to union. 要素
            y (int): The second object to union. 要素
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:  # すでに同じ親
            return
        # union by size
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        """returns the size of the group of x

        Args:
            x (int): The object to find the size of. 要素

        Returns:
            int: The size of the group of x.
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """returns True if the root of x is the same as the root of y

        Args:
            x (int): The first object to check. 要素
            y (int): The second object to check. 要素

        Returns:
            bool: True if the root of x is the same as the root of y.
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """returns the members of the group of x

        Args:
            x (int): The object to find the members of. 要素

        Returns:
            list: The members of the group of x.
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """returns the roots

        Returns:
            list: The roots.
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """returns the number of groups

        Returns:
            int: The number of groups.
        """
        return len(self.roots())

    def all_group_members(self):
        """returns all groups

        Returns:
            list: All group members.
        """
        return {r: self.members(r) for r in self.roots()}


def int1(x: int) -> int:
    return int(x) - 1


N, M = map(int, input().split())
A, B = [None] * M, [None] * M
for i in range(M):
    A[i], B[i] = map(int1, input().split())

uf = UnionFind(N)
cnt = 0
for i in range(M):
    a, b = A[i], B[i]
    if uf.find(a) == uf.find(b):
        cnt += 1
    uf.union(a, b)
print(cnt)