AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の26問目である「026 – Independent Set on a Tree(★4)」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します!
問題名 【026 – Independent Set on a Tree(★4)】
026 – Independent Set on a Tree(★4)
考察
今回は、どの頂点も隣り合わないように重複しないN//2頂点を取り出す問題です。
ここで、「どの頂点も隣り合わない」を言い換えると、「ある頂点から、2回移動して到達できる点」と言い換えることができます。なぜなら、隣接する頂点には、1回の移動で行けて、そこからもう一度移動した頂点は最初いた頂点と隣接しないからです。
もっというと、
- 任意の頂点から偶数回移動した頂点は、どの偶数回移動した頂点とも隣り合わない
- 任意の頂点から奇数回移動した頂点は、どの奇数回移動した頂点とも隣り合わない
です。(※一度探索したところには戻らないことを前提としています)
なので、今回は、幅優先探索(bfs)を行い、任意の頂点から奇数回で到達できる頂点を、-1(white)とし、偶数回で到達できる頂点を1(black)とします。
- 1(black)のnodeから1回の移動で到達できるnodeを-1(white)とする
- -1(white)のnodeから1回の移動で到達できるnodeを1(black)とする
上記の内容をbfsに盛り込んであげれば良いです。
典型解法:幅優先探索
コード
from collections import deque
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
def bfs(Node,start,N):
seen = [False]*N#初期情報
seen[start] = True#スタート位置には到達済み
dist = [1]*N#距離 ここでは、1が偶数回移動(blace) -1が奇数回移動(white)
que = deque()
que.append(start)
while que:
now = que.popleft()#取り出し
for next in Node[now]:#取り出した頂点から行ける場所を探索
if seen[next] == True:#すでに訪れたことがあれば探索しない
continue
elif seen[next] == False:#訪れたことがなかったら
seen[next] = True#今訪れたのでFalseに変換
dist[next] = dist[now]*-1#現在地と逆の色にする (-1をかけるとプラスマイナス入れ替わるから便利)
que.append(next)#新しくqueリストに追加
return dist
N = II()
[1 for i in range(N)]
edge = [[] for i in range(N)]
for i in range(N-1):
A,B = MI()
A-=1#0始まりにするため-1
B-=1#0始まりにするため-1
edge[A].append(B)#A頂点から移動できる頂点を追加
edge[B].append(A)#B頂点から移動できる頂点を追加
dist = bfs(edge,0,N)
black = []#0番目の頂点から偶数回移動した頂点を集める
white = []#0番目の頂点から奇数回移動した頂点を集める
for i in range(N):
if dist[i] == 1:
black.append(i+1)#0始まりにしていたので、+1してもとに戻す
else:
white.append(i+1)#0始まりにしていたので、+1してもとに戻す
if len(black) >= N//2:#黒い頂点が、n//2以上あるなら
print(*black[:N//2], sep=" ")
else:#黒い頂点が、n//2以下なら、白い頂点はn//2以上あるので
print(*white[:N//2], sep=" ")
まとめ
前の問題【024 – Select +/- One(★2)】
次の問題【027 – Sign Up Requests (★2)】
コメント