Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、16問目を解説していきたいと思います。
問題名 【D – Line++】
入力
N : 頂点の数かつ辺の数
X : 頂点Yとつながっている頂点
Y : 頂点Xとつながっている頂点
考察
KEY WORD 無向グラフ
無向グラフと言われたら、unionfind or bfs or dfsのどれかしらを使うことが多いイメージ
POINT 制約からコードをイメージ
今回、N < 2*10^3 です。
つまり、重めのfor文であっても一回までならネスト(for文の中にfor文をいれても)しても大丈夫です。
では今回、回すべきfor文は何でしょうか？
答え
2点間の距離なので、for文は「始点の位置」と「終点の位置」の2つについて全探索します。なので
- 1つ目のfor文 i番目を始点とした場合
- 2つ目のfor文 j番目を終点とした場合 の2点間の距離を求める
2点間の最短距離を求める際には、幅優先探索(bfs)を使用します。
(dfsも使用する場合もありますが、dfsを使った問題の時に詳しく述べますので、今は割愛します)
なので、上記の内容を実装すれば解くことができます。
コード
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)
N, X,Y = MI()
node = [[] for i in range(N)]
for i in range(1,N-1):
node[i].append(i-1)
node[i].append(i+1)
node[0].append(1)
node[N-1].append(N-2)
node[X-1].append(Y-1)
node[Y-1].append(X-1)
# for x in node:
# print(x)
def bfs(Node,start,N):
seen = [False]*N
seen[start] = True
dist = [0]*N
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
dist[next] += dist[now]+1
que.append(next)
return dist
cnt = [0]*(N)
for i in range(N):
a = bfs(node,i,N)
for j in a:
cnt[j] += 1
for i in range(1,N):
print(cnt[i]//2)まとめ
C-D問題の無向グラフのときは、大抵unionfind か bfs か dfsな気がする
コメント