AtCoder Beginner Contest 075 C – Bridge をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Beginner Contest 075 C – Bridge

Lowlinkを利用する手法で\(O(N+M)\)というのがあるらしいが、ここでは愚直に一つずつ外して確認している。計算量としては\(O(NM)\)なので、今回の制約下では問題ない。

# AtCoder Beginner Contest 075 C - Bridge
# https://atcoder.jp/contests/abc075/tasks/abc075_c
# tag: グラフ 連結 BFS DFS 橋 愚直

# 愚直に辺を一つずつ外し、連結になっているかどうか
# 確かめていく。

# 制約が緩いので、分かりやすさ優先で……
def main():
N, M = map(int, input().split())
path_dat = [list(map(int, input().split())) for _ in range(M)]

result = 0

for i in range(M):
# 対象の辺を外してグラフを構築、連結かどうか確認する
in_use = path_dat[:i] + path_dat[i+1:]

paths = [[] for _ in range(N)]
for a, b in in_use:
paths[a-1].append(b-1)
paths[b-1].append(a-1)

# ここから探索
visited = [False] * N
visited[0] = True
# 訪れた頂点数を記録していく
cnt = 1
queue = [0]
while queue:
now = queue.pop()
for nxt in paths[now]:
if visited[nxt]:
continue
visited[nxt] = True
queue.append(nxt)
cnt += 1

# 訪れた頂点数 != N なら、連結ではない
if cnt != N:
result += 1

print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です