結果

問題 No.2072 Anatomy
ユーザー kyskys
提出日時 2022-09-16 21:52:25
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 489 ms / 2,000 ms
コード長 2,418 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 87,072 KB
実行使用メモリ 100,708 KB
最終ジャッジ日時 2023-08-23 14:58:45
合計ジャッジ時間 8,806 ms
ジャッジサーバーID
(参考情報)
judge11 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
71,456 KB
testcase_01 AC 70 ms
71,344 KB
testcase_02 AC 74 ms
75,288 KB
testcase_03 AC 76 ms
75,412 KB
testcase_04 AC 73 ms
71,396 KB
testcase_05 AC 75 ms
75,140 KB
testcase_06 AC 74 ms
75,568 KB
testcase_07 AC 77 ms
75,432 KB
testcase_08 AC 471 ms
99,464 KB
testcase_09 AC 182 ms
95,516 KB
testcase_10 AC 379 ms
97,280 KB
testcase_11 AC 281 ms
96,988 KB
testcase_12 AC 247 ms
91,624 KB
testcase_13 AC 417 ms
98,384 KB
testcase_14 AC 351 ms
92,136 KB
testcase_15 AC 181 ms
89,488 KB
testcase_16 AC 419 ms
99,040 KB
testcase_17 AC 255 ms
96,524 KB
testcase_18 AC 175 ms
88,084 KB
testcase_19 AC 410 ms
98,920 KB
testcase_20 AC 489 ms
100,452 KB
testcase_21 AC 201 ms
97,416 KB
testcase_22 AC 408 ms
99,280 KB
testcase_23 AC 188 ms
97,216 KB
testcase_24 AC 190 ms
97,200 KB
testcase_25 AC 406 ms
100,708 KB
testcase_26 AC 70 ms
71,540 KB
testcase_27 AC 191 ms
96,872 KB
testcase_28 AC 341 ms
98,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

def main():
    from sys import stdin, setrecursionlimit
    # setrecursionlimit(1000000)
    input = stdin.readline
    def iinput(): return int(input())
    def sinput(): return input().rstrip()
    def i0input(): return int(input()) - 1
    def linput(): return list(input().split())
    def liinput(): return list(map(int, input().split()))
    def miinput(): return map(int, input().split())
    def li0input(): return list(map(lambda x: int(x) - 1, input().split()))
    def mi0input(): return map(lambda x: int(x) - 1, input().split())
    INF = 1000000000000000000
    MOD = 1000000007

    class UnionFindTree:
        def __init__(self, initial_size:int) -> None:
            self.n_nodes = initial_size
            self.parents = [i for i in range(initial_size)]
            self.ranks = [0 for i in range(initial_size)]
            self.size = [1 for i in range(initial_size)]
            self.n_roots = initial_size
        def root(self, n:int) -> int:
            if self.parents[n] == n:
                return n
            else:
                self.parents[n] = self.root(self.parents[n])
                return self.parents[n]
        def same(self, n:int, m:int) -> bool:
            return (self.root(n) == self.root(m))
        def unite(self, n:int, m:int) -> None:
            if self.same(n, m):
                return
            self.n_roots -= 1
            n, m = self.root(n), self.root(m)
            if self.ranks[n] < self.ranks[m]:
                self.parents[n] = m
                self.size[m] += self.size[n]
            else:
                self.parents[m] = n
                self.size[n] += self.size[m]
                if self.ranks[n] == self.ranks[m]:
                    self.ranks[n] += 1
        def get_roots(self) -> set:
            return set([self.root(x) for x in range(self.n_nodes)])
        def count_roots(self) -> int:
            return self.n_roots
        def get_tree_size(self, n:int) -> int:
            return self.size[self.root(n)]

    N, M = miinput()
    uf = UnionFindTree(N)
    UV = []
    for _ in [0] * M:
        u, v = mi0input()
        UV.append((u, v))
    
    ctr = [0] * N
    for u, v in UV[::-1]:
        u = uf.root(u)
        v = uf.root(v)
        if u == v:
            ctr[u] += 1
        else:
            uf.unite(u, v)
            r = uf.root(u)
            ctr[r] = max(ctr[u], ctr[v]) + 1
    print(max(ctr))
    

main()
0