ALDS1_11の解答例(Python)

深さ優先探索と幅優先探索に関する問題です． アルゴリズムについて詳しく知りたい方は参考文献などをご覧ください．

1. ALDS1_11_A: Graph

# ALDS1_11_A
n = int(input())

adj = [[0]*n for _ in range(n)] # 隣接行列
for _ in range(n):
    m = list(map(int,input().split(" ")))
    u,k,m = m[0],m[1],m[2:] # m=隣接リスト
    
    for x in m:
        adj[u-1][x-1] = 1
        
for x in adj:
    print(*x)

2. ALDS1_11_B: Depth First Search

# ALDS1_11_B
n = int(input())

# 隣接行列を作る
adj = [[0]*n for _ in range(n)]
for _ in range(n):
    m = list(map(int,input().split(" ")))
    u,k,m = m[0],m[1],m[2:]
    
    for x in m:
        adj[u-1][x-1] = 1

idx = 0
done_set = set() # 見つけた点のセット
cnt = 0 # 時刻
find_dict = {i:99999999 for i in range(n)} # 発見した時刻を記録する
end_dict = {i:99999999 for i in range(n)} # 終わった時刻を記録する
root_list = [] # 今までのルートを記録 探索が終わったかのどうかの判定に使う
while True:
    cnt += 1
    find_dict[idx] = min(cnt,find_dict[idx])
    done_set.add(idx) # 見つけたので調査済みに追加
    connect_list = adj[idx] # この点から行ける場所のリスト
    flag = False
    for i in range(n):
        # 行けて かつ 調査済みでない場合
        if connect_list[i] == 1 and i not in done_set:
            root_list.append(idx)
            idx = i
            flag = True
            break
    
    # 現在の位置から行ける点が全て調査済みの場合
    if not flag:
        # 全て調査済みなのでこの点は終了
        end_dict[idx] = cnt+1 # 同時に処理しているが発見と確認に1ターン差がないといけない
        # 戻って探索が必要な場合
        if root_list:
            idx = root_list.pop()
        # 戻ることができなければ全て終わっているかを調べる
        else:
            flag = True
            for i in range(n):
                # まだ調査が済んでいない場所があれば最小の点からスタートし直す
                if i not in done_set:
                    idx = i
                    flag = False
                    cnt += 1
                    break
                    
            if flag:
                break
            
            
for i in range(n):
    print(i+1,find_dict[i],end_dict[i])

3. ALDS1_11_C: Breadth First Search

# ALDS1_11_C
from collections import deque
n = int(input())

# 隣接行列を作る
adj = [[0]*n for _ in range(n)]
for _ in range(n):
    m = list(map(int,input().split(" ")))
    u,k,m = m[0],m[1],m[2:]
    
    for x in m:
        adj[u-1][x-1] = 1
        
find_dict = {i:-1 for i in range(n)} # 発見した時刻を記録する
find_dict[0] = 0

point_list = deque([[0,0]]) # 点のインデックスと何ターンで到達したかを記録
done_set = set([0])

while point_list:
    p,turn = point_list.popleft()
    
    for j in range(n):
        if adj[p][j] == 1:
            if j not in done_set:
                point_list.append([j,turn+1])
                find_dict[j] = turn+1
                done_set.add(j)
                
for i in range(n):
    print(i+1,find_dict[i])

4. ALDS1_11_D: Connected Components

# ALDS1_11_D
from collections import deque
n,m = map(int,input().split(" "))

relation = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split(" "))
    relation[a].append(b)
    relation[b].append(a)
    
# 幅優先探索
n = int(input())
relation_dict = {} # sから行ける人のリストの辞書
for _ in range(n):
    s,t = map(int,input().split(" "))
    if s in relation_dict.keys():
        pass
    else:
        point_list = deque([s]) # 点のインデックスを記録
        done_set = set([s])

        while point_list:
            p = point_list.popleft()

            for x in relation[p]:
                if x not in done_set:
                    point_list.append(x)
                    done_set.add(x)

        for x in done_set:
            relation_dict[x] = done_set
            
    if t in relation_dict[s]:
        print("yes")
    else:
        print("no")