AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Regular Contest 032 B – 道路工事
かつてはそれなりに難しかった問題、といった感じだろうか。単純に連結成分数を求める問題である。
# AtCoder Regular Contest 032 B - 道路工事
# https://atcoder.jp/contests/arc032/tasks/arc032_2
# tag: グラフ 連結成分 BFS DFS 大工のチョーさん
# 連結成分数が分かれば、その数 - 1 の道路を
# 作れば、全てを連結にできる。
def main():
N, M = map(int, input().split())
path_dat = [list(map(int, input().split())) for _ in range(M)]
# 隣接リストを作成
paths = [[] for _ in range(N)]
for a, b in path_dat:
a -= 1
b -= 1
paths[a].append(b)
paths[b].append(a)
# あらかじめ 1引いておく。
result = -1
# 連結成分数を数える。
visited = [False] * N
for start in range(N):
if visited[start] == True:
continue
result += 1
queue = [start]
while queue:
now = queue.pop()
for nxt in paths[now]:
if visited[nxt] == True:
continue
visited[nxt] = True
queue.append(nxt)
print(result)
main()
関連
