【AtCoder版！蟻本】ARC 037 B - バウムテスト【深さ優先探索】

AtCoder版！蟻本の深さ優先探索で類題としてあげられているARC037 BをPythonで解いていきます。
DFSを使ってグラフの連結成分に閉路があるか判別していきます。

リンク

atcoder.jp

AtCoder Regular Contest 037 B - バウムテスト

問題文

バウムテストとは、被験者に「木」の絵を描かせることで被験者の心理状態を読み取る心理検査である。この検査を受けた高橋君は、 N 個の頂点と M 本の辺からなる無向グラフを描いた。
このグラフの連結成分のうち木であるようなもの、すなわち閉路を持たないものの個数を求めよ。

制約

・ N (2 ≦ N ≦ 100)
・M (1 ≦ M ≦ N×(N−1)/2)
・ i+1 行目 (1 ≦ i ≦ M) には、辺 i が結ぶ 2 頂点の番号 ui, vi (1 ≦ ui ＜ vi ≦ N) がスペース区切りで与えられる。
・どの 2 頂点についても、それらを直接結ぶ辺は高々 1 本しか存在しない。

解答例

# 深さ優先探索
from collections import deque

n, m = map(int,input().split())

U = []
V = []
for i in range(m):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    U.append(u)
    V.append(v)

# 閉路を持たない木
ans = 0
# 探索済み頂点リスト
Visited = [0] * n

# 頂点iからdfs 探索済み頂点リストを更新していき 探索済み頂点をpopしたら閉路
def dfs(i):
    que = deque()
    que.append(i)       # 探索をはじめる頂点をpush
    flag = True         # 閉路判別フラグ Trueで閉路なし
    
    # queが空になるまで探索
    while len(que) != 0:
        k = que.pop()   # 探索する頂点kをpop
        if Visited[k] != 0:
            flag = False
        else:
            Visited[k] = 1    # 頂点kの探索済みリストを更新
            for j in range(m):
                # 未探索の頂点ならpush
                if U[j] == k and Visited[V[j]] == 0:
                    que.append(V[j])
                elif V[j] == k and Visited[U[j]] == 0:
                    que.append(U[j])
                
    #頂点iからの探索を終えたとき閉路があるかを返す
    return flag

# すべての頂点で未探索ならdfs
for l in range(n):
    if Visited[l] == 0:
        if dfs(l): # 探索して閉路がなければans+1
            ans += 1

print(ans)

解説

N個の頂点があり、2つの頂点をつなぐ辺がM本あるとき、辺でつながった連結成分のうち木である（閉路がない）ものの数を答える問題です。

0で初期化した探索済み頂点リストVisitedを作成し、DFSで探索していきます。
探索した頂点はVisitedの該当要素を+1してメモしていきました。

連結成分が木であるか閉路があるかの判断はVisitedを用います。
閉路があるときは探索済みの頂点がpopされますが、木である場合は探索済みの頂点がpopされることはないです。
これをflag管理して木である連結成分の数をカウントしていきました。

全頂点が探索済みとなればカウントしていた木の数を出力すればOKでした！

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク