結果

問題 No.1553 Lovely City
コンテスト
ユーザー kept1994
提出日時 2022-03-19 18:15:35
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,175 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 145,076 KB
最終ジャッジ日時 2024-10-04 23:27:28
合計ジャッジ時間 24,000 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 1 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
from collections import defaultdict
from os import sep
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.group_num = n
        self.parents = [-1] * n

    """ 要素xの値を取得。"""
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    """ 2つの要素の併合。"""
    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
        self.group_num -= 1
        return

    """ 要素xの属する集合の要素数を取得。"""
    def size(self, x):
        return -self.parents[self.find(x)]

    """ 2つの要素が同一の集合に属するか。"""
    def same(self, x, y):
        return self.find(x) == self.find(y)

    """ 要素xと同一の集合の要素を全取得。
    計算量 : O(N)
    """
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    """ 各集合の根を全取得。
    計算量 : O(N)
    """
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    """ 集合の個数を取得。 v2
    計算量 : O(1)
    """
    def group_count_v2(self):
        return self.group_num

    """ 集合の個数を取得。 v1
    計算量 : O(N)
    """
    def group_count_v1(self):
        return len(self.roots())

    """ 全集合の要素一覧を取得。
    計算量 : O(N)
    """
    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())

class Kruskal():
    def __init__(self, N: int) -> None:
        self.minimumG = [[] for _ in range(N)] # 全域最小木自体が欲しい場合にはこれを有効にする。
        self.edges = []
        self.uf =  UnionFind(N)
        self.minimunCost = 0
        return
    
    def addEdge(self, a: int, b: int, cost: int):
        self.edges.append((cost, a, b))
        return
    
    def build(self):
        for cost, a, b in sorted(self.edges):
            if self.uf.same(a, b):
                continue
            self.minimunCost += cost
            self.uf.union(a, b)
            # --- 全域最小木自体を構築 ---
            self.minimumG[a].append(b)
            # self.minimumG[b].append(a)
        return self.minimunCost
def main():
    N, M = map(int, input().split())
    tr = Kruskal(N)
    for _ in range(M):
        A, B = map(int, input().split())
        tr.addEdge(A - 1, B - 1, 1)
    tr.build()
    ans = []
    for i in range(N):
        for j in tr.minimumG[i]:
            ans.append(f"{i + 1} {j + 1}")
    print(len(ans))
    print(*ans, sep="\n")
    return

if __name__ == '__main__':
    main()
0