Yukicoder No.630 門松グラフ

微妙に未証明な気分のまま投げたが、解説として文字にしていたら自明ではという気分になった。

solution

二部グラフを作る。$O(N + M)$。

各点に書く自然数$a_i$は異なるとしてよい。重複があるまま門松グラフを作れるとすると容易に重複を除去できるため。 strictな大小関係$\lt$で辺に向きを付けて有向グラフを考える。 連結と仮定して、門松グラフであることと次が同値: 有向グラフと見たとき、入次数と出次数が共に正の頂点が存在しない。 入次数が正の頂点を赤かつ出次数が正の頂点を青で塗ることを考えれば、これは二部グラフ。

連結性が要求されていることに注意。

implementation

#!/usr/bin/env python3
n, m = map(int, input().split())
a = n // 2
b = n - a
if m < n - 1 or a * b < m:
    print('NO')
else:
    print('YES')
    print(*[ i + 1 for i in range(n) ])
    def edges():
        for i in range(a):
            yield ( i + 1, a + 1 )
        for i in range(a):
            for j in range(1, b):
                yield ( i + 1, a + j + 1 )
    for i, ( u, v ) in enumerate(edges()):
        if i == m:
            break
        print(u, v)