結果

問題 No.1640 簡単な色塗り
ユーザー lam6er
提出日時 2025-04-15 21:36:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,772 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 117,720 KB
最終ジャッジ日時 2025-04-15 21:38:24
合計ジャッジ時間 12,940 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))  # 1-based indexing
        self.size = [1] * (size + 1)
        self.edges = [0] * (size + 1)  # Number of edges in the component

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        # Path compression
        while self.parent[x] != root:
            parent = self.parent[x]
            self.parent[x] = root
            x = parent
        return root

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            self.edges[x_root] += 1
            return
        # Merge smaller component into larger one
        if self.size[x_root] < self.size[y_root]:
            x_root, y_root = y_root, x_root
        self.parent[y_root] = x_root
        self.size[x_root] += self.size[y_root]
        self.edges[x_root] += self.edges[y_root] + 1  # Add current edge


def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    A = []
    B = []
    for _ in range(N):
        a = int(input[ptr])
        b = int(input[ptr + 1])
        A.append(a)
        B.append(b)
        ptr += 2

    # Check if all balls are present in at least one operation
    exists = [False] * (N + 1)
    for a, b in zip(A, B):
        exists[a] = True
        exists[b] = True
    for x in range(1, N + 1):
        if not exists[x]:
            print("No")
            return

    # Check connected components using Union-Find
    uf = UnionFind(N)
    for a, b in zip(A, B):
        uf.union(a, b)

    # Collect all roots and check edges >= size
    roots = set()
    for x in range(1, N + 1):
        roots.add(uf.find(x))
    for root in roots:
        if uf.edges[root] < uf.size[root]:
            print("No")
            return

    # Determine the choices in reverse order
    used = [False] * (N + 1)
    ans = []
    # Iterate in reverse order of operations
    for a, b in reversed(list(zip(A, B))):
        if not used[a] and not used[b]:
            # Choose a
            choice = a
            used[a] = True
        elif not used[a]:
            choice = a
            used[a] = True
        elif not used[b]:
            choice = b
            used[b] = True
        else:
            # Both are used, choose arbitrarily (a)
            choice = a
        ans.append(choice)
    # Reverse to get the correct order
    ans = ans[::-1]

    # Verify all are used (should be guaranteed by earlier checks)
    for x in range(1, N + 1):
        if not used[x]:
            print("No")
            return

    print("Yes")
    for c in ans:
        print(c)


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