競プロ典型90問：026 - Independent Set on a Tree（★4）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_z

挑戦結果

• 挑戦日：2021/10/07
• 結果：解けた
• 時間：30分ぐらい

考えたこと

• 木なのでどこかのノードから距離を求めてしまえば求まりそう
• 距離0,2,4,6,・・・のノードは接続していない。
• 距離1,3,5,7,・・・のノードも接続してない。
• 距離が偶数 or 奇数のノードの集合で、数の多い方をN/2個並べればよい。

公式解説

• https://twitter.com/e869120/status/1387901052683386880

解説を読んだふりかえり

• 自分の考えも間違ってはなかったけど、二部グラフの性質として、2色(赤/緑)に塗り分けるほうがシンプルと思った。
• 自分はbfsで実装したけど、2色で塗るdfsの実装のほうが遥かにシンプルだった。
• 解説をみた翌日、解説の方針で実装し直してみた。
  • 再起の深さでREした。書きを追記した。
  • sys.setrecursionlimit(1000000)

ソース

最初に提出したもの

from collections import deque
N = int(input())
G = dict()
# グラフ用
for i in range(1,N+1):
    G[i] = set()
# インプットからグラフを作る
for _ in range(N-1):
    a,b = [int(x) for x in input().split()]
    G[a].add(b)
    G[b].add(a)

# 開始位置からの距離
D = {}
# 展開予定
opened = deque()
# すでに展開済み
visited = set()
# 開始位置
opened.append(1)
D[1] = 0
while len(opened) > 0:
    c = opened.popleft()
    visited.add(c) 
    for next in G[c]:
        if not next in visited:
            opened.append(next)
            D[next] = D[c]+1 

# 距離が偶数同士はつながっていない、奇数同士はつながっていない
# どちらか(数が多い方)をN//2個列挙すれば、隣り合わない頂点になっている。
L0 = []
L1 = []
for i in range(1,N+1):
    if D[i]%2==0:
        L0.append(i)
    else:
        L1.append(i)
L = L0 if len(L0) >= len(L1) else L1

# 出力
print(*L[0:N//2])

解説をみてから作り直した

from collections import deque

# 再起の深さを増やす
import sys
sys.setrecursionlimit(1000000)

N = int(input())
G = dict()
# グラフ用
for i in range(1,N+1):
    G[i] = set()
# インプットからグラフを作る
for _ in range(N-1):
    a,b = [int(x) for x in input().split()]
    G[a].add(b)
    G[b].add(a)

# 木を1 or 0で塗る。(未探索の初期値は-1)
C = [-1] * (N+1)

# 深さ優先で再帰的に色を塗る
def dfs(n, c):
    C[n] = c
    for next in G[n]:
        if C[next] == -1:
            dfs(next, 1-c)

# 頂点1から色を塗る
dfs(1,0)
# ０で塗ったもの、1で塗ったもののうち、
# 個数が大きい方をN//2個表示すればOK
ans0 =[]
ans1 =[]
for i, c in enumerate(C):
    if i>0:
        if c==0:
            ans0.append(i)
        else:
            ans1.append(i)
ans = ans0 if len(ans0) >= len(ans1) else ans1
# 出力
print(*ans[:N//2])