BOJ 2644カウント
5963 ワード
https://www.acmicpc.net/problem/2644
時間1秒、メモリ128 MB
input :全体人数n 二人の違う人の番号 親子関係の個数m 親子の関係を表す2つの番号x,y(xは後の整数yの親番号)output : 出力2人の整数 親戚関係が全くなく、世代を計算できない場合があります.-1出力探索を行うたびに、今何回目かを記録する変数があれば、寸法を記録することができます.
そしてチェックしやすいように、双方向のグラフで考えます.
どうせvisitで確認したから大丈夫
時間1秒、メモリ128 MB
input :
そしてチェックしやすいように、双方向のグラフで考えます.
どうせvisitで確認したから大丈夫
import sys
sys.setrecursionlimit(10000)
def dfs(now, cnt):
global ans
if now == target_two:
ans = cnt
return
for next_node in graph[now]:
if visit[next_node] == 0:
visit[next_node] = 1
dfs(next_node, cnt + 1)
n = int(sys.stdin.readline())
target_one, target_two = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]
for i in range(m):
x, y = map(int, sys.stdin.readline().split())
graph[x].append(y)
graph[y].append(x)
visit = [0] * (n + 1)
ans = -1
dfs(target_one, 0)
print(ans)
Reference
この問題について(BOJ 2644カウント), 我々は、より多くの情報をここで見つけました https://velog.io/@jsin2475/BOJ-2644-촌수계산テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol