結果
問題 |
No.2072 Anatomy
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()