#1060999 (PyPy3) No.1640 簡単な色塗り

• 問題: No.1640 簡単な色塗り
• ユーザー: LyricalMaestro
• 提出日時: 2025-03-28 23:53:31
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 434 ms / 2,000 ms
• コード長: 2,580 bytes
• コンパイル時間: 244 ms
• コンパイル使用メモリ: 82,488 KB
• 実行使用メモリ: 117,252 KB
• 最終ジャッジ日時: 2025-03-28 23:53:56
• 合計ジャッジ時間: 23,640 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 53

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
## https://yukicoder.me/problems/no/1640
from collections import deque
class UnionFind:
    """
    UnionFindの基本的な処理を実装したクラス
    """
    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.size = [1] * size
    def get_root(self, v):
        if v == self.root[v]:
            return v
        else:
            old_root = self.root[v]
            new_root = self.get_root(old_root)
            self.root[v] = new_root
            return new_root
    def merge(self, u, v):
        root_u = self.get_root(u)
        root_v = self.get_root(v)
        if root_u == root_v:
            return False
        if self.size[root_u] >= self.size[root_v]:
            self.size[root_u] += self.size[root_v]
            self.root[root_v] = root_u
            self.root[v] = root_u
        else:
            self.size[root_v] += self.size[root_u]
            self.root[root_u] = root_v
            self.root[u] = root_v
        return True
def main():
    N = int(input())
    edges = []
    for _ in range(N):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
    
    # まずは塗ることができるかの判定
    uf = UnionFind(N)
    rest_edges = []
    for i in range(N):
        a, b = edges[i]
        if not uf.merge(a, b):
            rest_edges.append(i)
    
    composites = {}
    for i in range(N):
        root_i = uf.get_root(i)
        composites[root_i] = 0
    
    for i in rest_edges:
        a, _ = edges[i]
        root_i = uf.get_root(a)
        composites[root_i] += 1
    
    for v in composites.values():
        if v != 1:
            print("No")
            return
    print("Yes")
    # ボールの塗り方を調べる
    next_nodes = [[] for _ in range(N)]
    for i in range(N):
        a, b = edges[i]
        next_nodes[a].append((b , i))
        next_nodes[b].append((a , i))
    answer = [-1] * N
    passed = [False] * N
    for edge_index in rest_edges:
        s, _ = edges[edge_index]
        queue = deque()
        queue.append(s)
        passed[s] = True
        while len(queue) > 0:
            v = queue.popleft()
            for w, i in next_nodes[v]:
                if i == edge_index:
                    continue
                if not passed[w]:
                    answer[i] = w + 1
                    passed[w] = True
                    queue.append(w)
        answer[edge_index] = s + 1
    for i in range(N):
        print(answer[i])
            
        
            
    
if __name__ == "__main__":
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX