結果

問題 No.3552 Triangular Coloring
コンテスト
ユーザー K2
提出日時 2026-05-22 23:27:14
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,298 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 306 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 265,996 KB
最終ジャッジ日時 2026-05-22 23:27:34
合計ジャッジ時間 10,706 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())

G = [set() for _ in range(N)]
edges = []
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edges.append((u, v))
    G[u].add(v)
    G[v].add(u)


def check(i):
    if len(G[i]) != 3:
        return False
    x, y, z = G[i]
    return x in G[y] and y in G[z] and z in G[x]

used = [False] * N
ok = set(filter(check, range(N)))
child = defaultdict(list)

while ok:
    i = ok.pop()
    used[i] = True
    idx = sorted(G[i])
    for x in idx:
        if check(x):
            ok.remove(x)
    for x in idx:
        G[x].remove(i)
        if check(x):
            ok.add(x)
    G[i].clear()
    k = tuple(idx)
    child[k].append(i)

cur = tuple(sorted(filter(lambda i: not used[i], range(N))))
assert len(cur) == 3

color = [-1] * N
color[cur[0]] = 1
color[cur[1]] = 2
color[cur[2]] = 3


def dfs(cur):
    x, y, z = cur
    c = 10 - sum(color[k] for k in cur)
    for i in child[cur]:
        color[i] = c
        dfs(tuple(sorted((x, y, i))))
        dfs(tuple(sorted((y, z, i))))
        dfs(tuple(sorted((z, y, i))))


dfs(cur)

# assert all(1 <= c <= 4 for c in color)
# assert all(color[u] != color[v] for u, v in edges)

print("Yes")
print(*color)
0