結果
問題 |
No.1640 簡単な色塗り
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:48:07 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,037 bytes |
コンパイル時間 | 289 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 130,176 KB |
最終ジャッジ日時 | 2025-03-26 15:49:36 |
合計ジャッジ時間 | 13,073 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 WA * 27 |
ソースコード
import sys sys.setrecursionlimit(1 << 25) def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]) idx += 1 A = [] B = [] for _ in range(N): a = int(data[idx]) b = int(data[idx+1]) A.append(a) B.append(b) idx += 2 # Check if all balls are present present = [False] * (N + 1) for a, b in zip(A, B): present[a] = True present[b] = True for v in range(1, N + 1): if not present[v]: print("No") return # Union-Find structure to manage connected components parent = list(range(N + 1)) size = [1] * (N + 1) edge_count = [0] * (N + 1) def find(u): while parent[u] != u: parent[u] = parent[parent[u]] u = parent[u] return u for a, b in zip(A, B): root_a = find(a) root_b = find(b) if root_a == root_b: edge_count[root_a] += 1 else: if size[root_a] < size[root_b]: root_a, root_b = root_b, root_a parent[root_b] = root_a size[root_a] += size[root_b] edge_count[root_a] += edge_count[root_b] + 1 # Check if each component's size equals edge count roots = set() for v in range(1, N + 1): roots.add(find(v)) valid = True for root in roots: if size[root] != edge_count[root]: valid = False break if not valid: print("No") return # Greedy selection selected = [False] * (N + 1) ans = [] for i in range(N): a = A[i] b = B[i] if not selected[a]: selected[a] = True ans.append(a) elif not selected[b]: selected[b] = True ans.append(b) else: print("No") return print("Yes") for num in ans: print(num) if __name__ == "__main__": main()