結果

問題 No.2072 Anatomy
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:53:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 404 ms / 2,000 ms
コード長 1,330 bytes
コンパイル時間 349 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 130,104 KB
最終ジャッジ日時 2025-03-31 17:54:39
合計ジャッジ時間 7,971 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    edges = []
    for _ in range(M):
        u = int(input[ptr])
        ptr += 1
        v = int(input[ptr])
        ptr += 1
        edges.append((u, v))
    
    # Process edges in reversed order (highest-numbered first)
    sorted_edges = reversed(edges)
    
    parent = list(range(N + 1))  # 1-based indexing
    steps = [0] * (N + 1)
    rank = [1] * (N + 1)
    
    def find(u):
        if parent[u] != u:
            parent[u] = find(parent[u])
        return parent[u]
    
    max_step = 0
    for u, v in sorted_edges:
        ru = find(u)
        rv = find(v)
        if ru != rv:
            # Ensure ru is the smaller rank to merge into rv
            if rank[ru] > rank[rv]:
                ru, rv = rv, ru
            parent[ru] = rv
            current_step = max(steps[ru], steps[rv]) + 1
            steps[rv] = current_step
            if rank[ru] == rank[rv]:
                rank[rv] += 1
        else:
            current_step = steps[ru] + 1
            steps[ru] = current_step
        if current_step > max_step:
            max_step = current_step
    print(max_step)

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