競プロ典型90問 自習3

スポンサーリンク
AtCoder
スポンサーリンク

競技プログラミングAtCoderのレベルアップのため、競プロ典型問題をPythonで解いていきます。
時間対効果を最大にするために以下のスキームで行います。
①問題を見る②10分だけ自力で考える③解説をみる④解説を見ながら、周辺知識を補完して、自力でコードを書く⑤問題を解く⑥他の方のコードを見て参考にして学習する⑦ブログにまとめる

003 – Longest Circular Road(★4)

キーワード:「グラフ」、「幅優先探索(BFS)」、「探索部分のクラス化」、「スタックの実装」

見直し後の解答

from collections import deque
from sys import stdin
input = stdin.readline

n = int(input())

# map作成
G = [list() for _ in range(n)]

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

# 始点からBFS
class Distance_Checker:
	def __init__(self, start):
		self.arrived = [-1] * n	
		self.todo = deque([start])
		self.arrived[start] = 1
		self._add_list()

	def _add_list(self):
		while self.todo:
			pos = self.todo.popleft()
			depth = self.arrived[pos]

			for p in G[pos]:
				if self.arrived[p] == -1:
					self.todo.append(p)
					self.arrived[p] = depth + 1
			depth += 1
		return

# 実行部
first_check = Distance_Checker(0)
next_pos = first_check.arrived.index(max(first_check.arrived))
second_check = Distance_Checker(next_pos)
print(max(second_check.arrived))

ポイント深堀

グラフ

N個の点を、M本の経路で結ぶ。向きがないので、無向グラフ。すべてがつながって 閉路がないので、ツリー構造。無向グラフの実装は、入と出の両方向をグラフ(G)のリストに追加して実装。(他のパターンのグラフ:参考

# map作成
G = [list() for _ in range(n)]

for i in range(n-1):
	a, b = map(int, input().split())
	G[a-1].append(b-1)
	G[b-1].append(a-1)
幅優先探索

グラフのリスト(G)を元に網羅的なグラフをたどる。一回行ったところは、マークを付ける。今回の問題の場合は距離をマークする(未到達要素は-1で表現)。

探索部分のクラス

今回は任意の1点から、最長の点を探した後に、その点から、最長の点を探索することで、最も遠い2点を探索する。探索は2回行うので、クラスで再利用可能にした。

スタックの実装

探索すべきノードをスタックに入れて、先に入ったものから先に探索するようにする。普通のリストだと、popでは一番最後に入ったものしか取り出せないし、一番先頭の値を取り出すとリストのインデックスをふりなおすことになって、リストの要素数分だけ、余分な計算が必要。「collections」ライブラリの 「deque」関数を使うことにより、素早く「popleft()」で先頭から値を取り出すことができる。

from collections import deque

# 始点からBFS
class Distance_Checker:
	def __init__(self, start):
		self.arrived = [-1] * n	
		self.todo = deque([start])
		self.arrived[start] = 1
		self._add_list()

	def _add_list(self):
		while self.todo:
			pos = self.todo.popleft()
			depth = self.arrived[pos]

			for p in G[pos]:
				if self.arrived[p] == -1:
					self.todo.append(p)
					self.arrived[p] = depth + 1
			depth += 1
		return

# 実行部
first_check = Distance_Checker(0)
next_pos = first_check.arrived.index(max(first_check.arrived))
second_check = Distance_Checker(next_pos)
print(max(second_check.arrived))
AtCoder
スポンサーリンク

コメント