結果

問題 No.1390 Get together
コンテスト
ユーザー itsy68
提出日時 2022-09-02 20:02:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 467 ms / 2,000 ms
コード長 4,372 bytes
コンパイル時間 433 ms
コンパイル使用メモリ 82,000 KB
実行使用メモリ 110,336 KB
最終ジャッジ日時 2024-11-16 00:38:12
合計ジャッジ時間 12,328 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from itertools import combinations, permutations, product, accumulate, groupby
from collections import defaultdict, deque, Counter
from functools import reduce
import heapq
import bisect
import math
import copy

sys.setrecursionlimit(10 ** 9)
input = lambda: sys.stdin.readline().rstrip()
INF = float("inf")
MOD = 10 ** 9 + 7
# DFS
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')

# https://algo-method.com/descriptions/136
class UnionFind():
    # 初期化
    def __init__(self, n):
        self.par = [-1] * n
        self.rank = [0] * n
        self.siz = [1] * n
        # 新たな配列
        self.min_node = [i for i in range(n)]
    # 根を求める
    def root(self, x):
        if self.par[x] == -1: return x # x が根の場合は x を返す
        else:
          self.par[x] = self.root(self.par[x]) # 経路圧縮
          return self.par[x]

    # x と y が同じグループに属するか (根が一致するか)
    def issame(self, x, y):
        return self.root(x) == self.root(y)

    # x を含むグループと y を含むグループを併合する
    def unite(self, x, y):
        # x 側と y 側の根を取得する
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: return False # すでに同じグループのときは何もしない
        # union by rank
        if self.rank[rx] < self.rank[ry]: # ry 側の rank が小さくなるようにする
            rx, ry = ry, rx
        self.par[ry] = rx # ry を rx の子とする
        if self.rank[rx] == self.rank[ry]: # rx 側の rank を調整する
            self.rank[rx] += 1
        self.siz[rx] += self.siz[ry] # rx 側の siz を調整する
        # min_node の更新
        self.min_node[rx] = min(self.min_node[rx], self.min_node[ry])
        
        return True
    
    # x を含む根付き木のサイズを求める
    def size(self, x):
        return self.siz[self.root(x)]

    # 追加: x を含む根付き木の中での頂点番号の最小値
    def get_min_node(self, x):
        return self.min_node[self.root(x)]


import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter, deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as Gcd
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
from collections import defaultdict


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, 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):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        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):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())


N, M = map(int, input().split())
UF = UnionFind(M)
L = [[] for i in range(N)]
for i in range(N):
    b, c = map(int, input().split())
    b-=1
    c-=1
    L[c].append(b)
count = 0
for l in L:
    for b in l:
        if not UF.same(l[0], b):
            UF.union(l[0], b)
            count += 1
print(count)
0