GRL_4の解答例(Python)

閉路検出とトポロジカルソートに関する問題です．

1. GRL_4_A: Cycle Detection for a Directed Graph

# GRL_4_A
# 「s から t に到達できる」 かつ 「t から sに到達できる」ならば閉路
from collections import deque

def main():
    V,E = map(int,input().split())
    adjacent_list = [[] for _ in range(V)]

    for _ in range(E):
        s,t = map(int,input().split())
        adjacent_list[s].append((s,t))

    # それぞれの点に対して到達できる点を調べる
    done_set_list = []
    for i in range(V):
        d = deque(adjacent_list[i])
        done_set = set()
        while d:
            s,t = d.popleft()
            if t not in done_set:
                done_set.add(t)
                for s2,t2 in adjacent_list[t]:
                    d.appendleft((s2,t2))

        # i から到達できる点の集合をdone_set_listに追加
        done_set_list.append(done_set)

    # s から t に到達できる かつ t から sに到達できるなら閉路
    for s in range(V):
        for t in done_set_list[s]:
            if t == s:
                return 1 

    return 0

main()

2. GRL_4_B: Topological Sort

# GRL_4_B: Topological Sort
# 単純に深さ優先探索の終了時刻を逆順に表示すればトポロジカルソートになる
from collections import deque
def DFS_time(u,done_set,cnt,time_dict,finish_dict,adjacent_list):
    delta = set()
    S = deque()
    S.append(u) # 始点をスタックに追加
    done_set.add(u)
    delta.add(u)
    time_dict[u] = cnt # 訪問時間を代入する

    while S:
        u = S[-1]
        if adjacent_list[u]:
            u,v = adjacent_list[u].pop() # uに隣接している頂点を取得する
            if v not in done_set:
                done_set.add(v)
                delta.add(v)
                S.append(v)
                cnt += 1
                time_dict[v] = cnt # 訪問時間を記録
                appended = True
        # 隣接する頂点がない場合   
        else:
            S.pop()
            cnt += 1
            finish_dict[u] = cnt # 探索が終わった時間を記録
            
    return time_dict,finish_dict,done_set,cnt,delta

V,E = map(int,input().split())
# グラフを隣接リストとして受け取る
adjacent_list = [[] for _ in range(V)]
inversed_list = [[] for _ in range(V)] # 向きを逆にした隣接リスト
for _ in range(E):
    s,t = map(int,input().split())
    adjacent_list[s].append((s,t)) 
    inversed_list[t].append((t,s)) 
    
all_set = set([i for i in range(V)])
done_set = set()
cnt = 0
time_dict = {}
finish_dict = {}
while all_set:
    s = list(all_set)[0]
    time_dict,finish_dict,done_set,cnt,delta = DFS_time(s,done_set,cnt,time_dict,finish_dict,adjacent_list)
    all_set -= done_set
    # print(time_dict,finish_dict,done_set,cnt,all_set)
    
# 終了時刻の遅い順に並べる
# print(finish_dict)
key_values = sorted(finish_dict.items(), key=lambda x:-x[1])

for key_value in key_values:
    print(key_value[0])