トップページ -> AOJの解答例 -> GRL_3の解答例

GRL_3の解答例(Python)

関節点(切断点)，橋，強連結成分分解に関する問題です．

1. GRL_3_A: Articulation Points

関節点(切断点)を見つける問題です．この方法では間に合いませんが，rを始点とした深さ優先探索をしたときに子が2つ以上あれば関節点です．


# GRL_3_A
# 間に合わないけど単純なやつ
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)) 
        adjacent_list[t].append((t,s)) 
    
    for r in range(V):
        print(r)
        # 始点rに対して深さ優先探索をする
        queue = deque(adjacent_list[r])
        done_set = set([r]) # 巡回済みの点の集合

        # すべての点を始点にしてみて子が何個あるかを調べる
        while queue:
            s,t = queue.pop()
            # sが始点で巡回済みでない点が見つかった場合(2つ以上の子がある)
            if len(done_set) > 1:
                if s == r and t not in done_set:
                    print(r)
                    break

            if t not in done_set:
                done_set.add(t)
                for info in adjacent_list[t]:
                    s,t = info
                    if t not in done_set:
                        queue.append(info)

main()

この方法では間に合わないので LowLink で関節点を求めました．グラフ探索アルゴリズムとその応用の38ページの疑似コードを参考に書きました．


# GRL_3_A

import sys
# 再帰回数の上限を変更
sys.setrecursionlimit(20000)

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)) 
    adjacent_list[t].append((t,s)) 
    
done_set = set([0]) # 巡回済みの点
done_edge = set() # 深さ優先探索で使用した辺(これに入っていなければ後退辺)
low_time = {i:float("inf") for i in range(V)} # Lowlinkのlow
find_time = {i:float("inf") for i in range(V)} # 発見した時刻
k = 0 # 時刻を管理する
ans = set() # 関節点の集合

# 深さ優先探索
def DFS(u):
    global k
    find_time[u] = k
    low_time[u] = k
    # 根で子が2つ以上(2回目の探索)ならば関節点
    if u == 0 and k != 0:
        ans.add(u)
    k += 1
    
    # u と隣接する点に関して
    for info in adjacent_list[u]:
        u,v = info
        if v not in done_set:
            done_set.add(v)
            done_edge.add(f"{u} {v}")
            done_edge.add(f"{v} {u}")
            if u == 0 and k != 1:
                ans.add(u)
            DFS(v)
            low_time[u] = min(low_time[u],low_time[v])
            # 根以外でuのある子vに対してfind_time[u] <= low_time[v]ならば関節点
            if u != 0:
                if find_time[u] <= low_time[v]:
                    ans.add(u)
        # 後退辺ならばlowを更新
        elif f"{u} {v}" not in done_edge:
            low_time[u] = min(low_time[u],find_time[v])
            
DFS(0)

ans = sorted(list(ans))
for a in ans:
    print(a)

2. GRL_3_B: Bridges

橋を求める問題です． Aの条件が根も含めてuのある子vに対してfind_time[u] < low_time[v]ならば橋に変わっただけです．


# GRL_3_B

import sys
# 再帰回数の上限を変更
sys.setrecursionlimit(20000)

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)) 
    adjacent_list[t].append((t,s)) 
    
done_set = set([0]) # 巡回済みの点
done_edge = set() # 深さ優先探索で使用した辺(これに入っていなければ後退辺)
low_time = {i:float("inf") for i in range(V)} # Lowlinkのlow
find_time = {i:float("inf") for i in range(V)} # 発見した時刻
k = 0 # 時刻を管理する
ans = [] # 橋のリスト

# 深さ優先探索
def DFS(u):
    global k, done_set, done_edge, low_time, find_time
    find_time[u] = k
    low_time[u] = k
    # 根で子が2つ以上(2回目の探索)ならば関節点
    if u == 0 and k != 0:
        ans.add(u)
    k += 1
    
    # u と隣接する点に関して
    for info in adjacent_list[u]:
        u,v = info
        if v not in done_set:
            done_set.add(v)
            done_edge.add(f"{u} {v}")
            done_edge.add(f"{v} {u}")
            DFS(v)
            low_time[u] = min(low_time[u],low_time[v])
            # 根も含めてuのある子vに対してfind_time[u] < low_time[v]ならば橋
            if find_time[u] < low_time[v]:
                ans.append((min(u,v),max(u,v)))
        # 後退辺ならばlowを更新
        elif f"{u} {v}" not in done_edge:
            low_time[u] = min(low_time[u],find_time[v])
            
DFS(0)

ans = sorted(list(ans))
for a in ans:
    print(*a)

3. GRL_3_C: Strongly Connected Components

強連結成分分解をする問題です．与えられたグラフと辺の向きを逆にしたグラフに対して1回ずつ深さ優先探索を行っています．
引数がぐちゃぐちゃであまりにも酷いのでそのうち書き直します...
【外部サイト】強連結成分分解の意味とアルゴリズム


# GRL_3_C

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])

all_set = set([i for i in range(V)])
done_set = set()
cnt = 0
linked_dict = {}
for key_value in key_values:
    key,value = key_value
    if key in all_set:
        # 終了時刻の遅い順に深さ優先探索(逆向き)
        time_dict,finish_dict,done_set,cnt,delta = DFS_time(key,done_set,cnt,time_dict,finish_dict,inversed_list)
        all_set -= done_set
        # print(done_set)
        
        for s in delta:
            linked_dict[s] = delta
            
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    if t not in linked_dict[s]:
        print(0)
    else:
        print(1)

<- 前へ戻る【目次に戻る】次へ進む ->