結果

問題 No.3552 Triangular Coloring
コンテスト
ユーザー 👑 loop0919
提出日時 2026-05-05 00:35:36
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 903 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 192 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 250,044 KB
最終ジャッジ日時 2026-05-22 21:48:39
合計ジャッジ時間 12,731 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 16 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque
from random import randint

INF = 10**18

N, M = [int(s) for s in input().split()]
graph = [[] for _ in range(N)]

for _ in range(M):
    u, v = [int(s) - 1 for s in input().split()]
    graph[u].append(v)
    graph[v].append(u)

del_graph = [set(graph[v]) for v in range(N)]
three = [v for v in range(N) if len(graph[v]) == 3]

order = []
connected = []

while three:
    curr = three.pop()
    order.append(curr)
    to_vs = del_graph[curr].copy()

    connected.append(to_vs)

    for to in to_vs:
        del_graph[to].discard(curr)

        if len(del_graph[to]) == 3:
            three.append(to)

order = order[::-1]
connected = connected[::-1]

answers = [None] * N
answers[order[0]] = 1
answers[order[1]] = 2
answers[order[2]] = 3

for curr, vs in zip(order[3:], connected[3:]):
    answers[curr] = ({1, 2, 3, 4} - {answers[v] for v in vs}).pop()

print(*answers)
0