[Python] DFS ABC199D

ABC199D

$3^N$ 通りの塗り方を全部探索する方法では実行時間制限に間に合わせるのは困難です。
ある頂点iの色を決めた時、iと辺で繋がっている頂点の色の探索候補は2通りしかないから、グラフが連結なら$3×2^{N-1}$通りの塗り方だけ探索すればよい。
今回グラフは連結とは限りませんが、連結成分ごとの塗り方の数の積が全体の塗り方の数となるので連結成分ごとに処理すればグラフが連結な場合に帰着することができます。

サンプルコード

import copy
n,m=map(int,input().split())
G=[[] for _ in range(n)]
# 隣接グラフ設定
for i  in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    G[a].append(b)
    G[b].append(a)

done=[False]*n   # 頂点のグラフ作成済みフラグ

# 再帰で連結グラフ作成
def make_union(p,ret):
    done[p]=True
    ret.append(p)
    for q in G[p]:
        if done[q]: continue
        make_union(q,ret)
    return ret

"""
連結グラフの頂点iから再帰DFSで色を塗り、塗り方が何通りか返す
stateは色塗状況、lstは連結グラフ
"""
def dfs(i,state,lst):
    ret=0
    # 終端処理
    if i+1==len(lst):
        for c in range(3):
            for q in G[lst[i]]:
                if state[q]==c: break
            else: ret+=1
        return ret
    for c in range(3):
        state[lst[i]]=c
        for q in G[lst[i]]:
            if state[q]==c: break
        else:
            ret+=dfs(i+1,copy.copy(state),lst)
    return ret

ans=1
for p in range(n):
    if done[p]: continue # 数え済みならパス
    lst=make_union(p,[])
    ans*=dfs(0,[-1]*n,lst)
print(ans)