典型90 026 – Independent Set on a Tree（★4）

競プロの精進のために学びがあった問題についてまとめています。目標は AtCoder 水色！

今のレートは茶色です。

問題

典型90 026 – Independent Set on a Tree（★4）を解きました。

考察

「N 頂点の木」が与えられるということから、必ず子を持たない頂点と根となる頂点が存在しているはずである。

ここで、隣合わない頂点とは、その頂点が存在する深さの偶奇が同じ場合であるといえる。

つまり、根となる頂点を見つけ出し、そこから木構造をたどっていく際に、深さの偶奇が同じ頂点をまとめていけば、重複しない頂点を取り出すことができる。

と思ったのですが、上記の方法では解くことができませんでした。

この問題のポイントは、「2部グラフ」の性質を使う、というものです。

2部グラフとは、「各頂点を白または黒に塗り分けることが可能なグラフ」を指します。

ここで、白色の頂点は黒色の頂点と隣接することがなく、黒色の頂点も同じく白色の頂点と隣接しません。

あるグラフが2部グラフかどうかを判定するためには、深さ優先探索を用いて、ある点と隣接する点をすべて同じ色に塗ったときにすべての点が黒か白かで塗り分けられることを確認すれば良い

コード

from collections import deque

def dfs(N, next_node):
    if Seen[next_node]:
        return
    Seen[next_node] = True
    C = Color[next_node]
    if C:
        C = False
    else:
        C = True
    for i in range(len(V[next_node])):
        ne = V[next_node][len(V[next_node]) - 1 - i]
        if not Seen[ne]:
            stack.append(ne)
            Color[ne] = C
            if C:
                White.append(ne)
            else:
                Black.append(ne)
    return

N = int(input())
C = True
White = []
Black = []
Color = [-1 for i in range(N+1)]
Node = [[] for i in range(N+1)]

for i in range(1, N):
    a,b = map(int,input().split())
    Node[a].append(b)
    Node[b].append(a)

# dfs
V = Node
stack = deque()
Seen = [False for i in range(N+1)]
Time = 0
Color[1] = C
White.append(1)
stack.append(1)

while stack:
    next_node = stack.pop()
    dfs(N, next_node)


if len(White) > len(Black):
    White.sort()
    for i in range(N//2):
        print("{} ".format(White[i]), end="")
else:
    Black.sort()
    for i in range(N//2):
        print("{} ".format(Black[i]), end="")