#936173 (PyPy3) No.2563 色ごとのグループ

提出ソース

結果

問題	No.2563 色ごとのグループ
ユーザー	21kazu13
提出日時	2023-12-04 14:25:39
言語	PyPy3 (7.3.15)
結果	AC
実行時間	406 ms / 2,000 ms
コード長	5,931 bytes
コンパイル時間	539 ms
コンパイル使用メモリ	81,700 KB
実行使用メモリ	132,800 KB
最終ジャッジ日時	2023-12-04 14:25:49
合計ジャッジ時間	8,131 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	57 ms 65,788 KB
testcase_01	AC	55 ms 65,788 KB
testcase_02	AC	56 ms 65,788 KB
testcase_03	AC	56 ms 65,788 KB
testcase_04	AC	56 ms 65,788 KB
testcase_05	AC	56 ms 65,788 KB
testcase_06	AC	57 ms 65,788 KB
testcase_07	AC	56 ms 65,788 KB
testcase_08	AC	57 ms 65,788 KB
testcase_09	AC	58 ms 65,788 KB
testcase_10	AC	57 ms 65,788 KB
testcase_11	AC	57 ms 65,788 KB
testcase_12	AC	57 ms 65,788 KB
testcase_13	AC	56 ms 65,788 KB
testcase_14	AC	92 ms 77,424 KB
testcase_15	AC	83 ms 77,544 KB
testcase_16	AC	82 ms 77,424 KB
testcase_17	AC	74 ms 74,488 KB
testcase_18	AC	71 ms 73,208 KB
testcase_19	AC	83 ms 77,544 KB
testcase_20	AC	99 ms 79,328 KB
testcase_21	AC	95 ms 78,280 KB
testcase_22	AC	92 ms 77,900 KB
testcase_23	AC	95 ms 78,156 KB
testcase_24	AC	200 ms 90,612 KB
testcase_25	AC	171 ms 92,332 KB
testcase_26	AC	229 ms 105,936 KB
testcase_27	AC	255 ms 125,464 KB
testcase_28	AC	236 ms 111,316 KB
testcase_29	AC	325 ms 127,824 KB
testcase_30	AC	289 ms 127,824 KB
testcase_31	AC	287 ms 127,824 KB
testcase_32	AC	287 ms 127,824 KB
testcase_33	AC	373 ms 132,560 KB
testcase_34	AC	363 ms 132,800 KB
testcase_35	AC	406 ms 132,412 KB
testcase_36	AC	372 ms 132,560 KB
testcase_37	AC	374 ms 132,560 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right, insort_left, insort_right  # type: ignore
from collections import Counter, defaultdict, deque  # type: ignore
from math import gcd, sqrt, ceil, factorial  # type: ignore
from heapq import heapify, heappop, heappush, heappushpop, heapreplace, merge  # type: ignore
from itertools import accumulate, combinations, permutations, product  # type: ignore
from string import ascii_lowercase, ascii_uppercase # type: ignore

def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode("utf-8").split()
def S(): return sys.stdin.buffer.readline().rstrip().decode("utf-8")
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def SRL(n): return [list(S()) for _ in range(n)]

class UnionFind():
    def __init__(self, n):
        '''
        Class for union find
        Args:
            n (int): number of nodes
        Attributes:
            n (int): number of nodes
            parents (list): parent of each nodes. If nodes are root, it returns negative value and its absolute value is member count.
            group_count (int): number of groups in UF
        '''
        self.n = n
        # parents[m]が非負整数であれば親のnodeを示す
        # 負であればrootであることを示し、その絶対値は自分を含んだ要素数を示す
        # unionメソッドでどっちにくっつけるかの判定に用いる
        self.parents = [-1] * n
        self.group_count = n

    def isroot(self,x):
        '''
        Check if node is root: O(1)
        Args:
            x (int): node number
        Returns:
            bool: True if node is root. False if node is not root.
        '''
        return True if self.parents[x] < 0 else False
    
    def find(self, x):
        '''
        Find root for node: O(a(n))
        Args:
            x (int): node number
        Returns:
            int: root number of node x
        '''
        if self.parents[x] < 0:
            # 負であればrootなのでrootのnode番号を返す
            return x
        else:
            # 正であればその親のnodeを探す
            # その際parents[x]の値をroot直通にする
            # 経路圧縮
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        '''
        Union two nodes into one group
        Args:
            x (int): node number
            y (int): node number
        Returns:
            Nothing
        '''
        # x,yそれぞれのrootを見つけ、置き換える
        x = self.find(x)
        y = self.find(y)
        
        # 同一であれば何もしない
        if x == y:
            return

        # 異なっていれば、サイズの大きい方に小さい方をくっつける
        # findの経路圧縮をできるだけ少なく(計算し直すものが少なくなる)できるようなイメージ
        # x,yはrootなので、yの方がサイズ数が大きい(負なので値としては小さくなる)場合はx,yをswap
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        # xにyをくっつけ(サイズの更新)、yの親をに置き換える
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.group_count -= 1

    def same(self, x, y):
        '''
        Confirm two nodes have same root or not
        Args:
            x (int): node number
            y (int): node number
        Returns:
            (bool): True in case both have the same root, False in the other case.
        '''
        # rootを探して同一ならtrue
        return self.find(x) == self.find(y)

    def size(self, x):
        '''
        Get the group size in x
        Args:
            x (int): node number
        Returns:
            (int): Size (member count) in the group of x
        '''
        # rootを探して格納されている要素数を返す
        return -self.parents[self.find(x)]

    def members(self, x):
        '''
        Get the all group members in x: O(n)
        Args:
            x (int): node number
        Returns:
            (list): nodes who are in group of x
        '''
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        '''
        Get all roots in UF: O(n)
        Args:
            Nothing
        Returns:
            (list): list which all roots includes in
        '''
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        # 各rootに対してそれに属するnodeをdict形式で格納する
        # 存在しないkeyを渡すと[]が取得でき格納されるdict
        group_members = defaultdict(list)
        # 各nodeに対してどのrootに属しているかを
        for member in range(self.n):
            #group_members[nodeのroot]がリストなので、それに対してnodeを追加する
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        # 上で求めたdict形式の可視化
        # __str__のオーバーライドなのでprint(instance)がこの形式で出力される
        # root: [node,node,...]
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

N,M = LI()
uf = UnionFind(N)
colors = [[] for _ in range(N)]
C = LI()
for idx,c in enumerate(C):
    colors[c-1].append(idx)

for _ in range(M):
    u,v = LI()
    u-=1
    v-=1
    if C[u]==C[v]:
        uf.union(u,v)

ans = 0
for l in colors:
    cnt = set([uf.find(v) for v in l])
    ans += max(0,len(cnt)-1)
print(ans)

yukicoder

結果

テストケース

ソースコード