グラフ典型問題

グラフ問題の考察や解法でよく使いそうなものをメモ。

連結成分の個数を数える
閉路検出
- 参考サイト
木構造
- 頂点の深さ計測
- 参考サイト
最短経路＆経路復元＆距離計測

連結成分の個数を数える

全ての頂点から探索を開始して、未探索のものがあれば、連結成分の個数としてカウント

例えば、下図の場合は１から探索開始。連結成分＋１。
↓
１，２，３が探索済みになる。
↓
２から探索開始→探索済みなのでスルー
↓
３から探索開始→探索済みなのでスルー
↓
４から探索開始→未探索なので連結成分＋１。

サンプルコード（無向グラフ）

import sys
sys.setrecursionlimit(10**6)

# n=頂点数　m=辺の数
n, m = map(int, input().split())
g = [[] for _ in range(n)]
seen = [False]*n

def dfs(num):
    seen[num] = True
    for next in g[num]:
        if seen[next]:
            continue
        dfs(next)

# g[頂点番号][ここから繋がる頂点番号]
for i in range(m):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

#連結成分の個数を数える
renketu = 0
for i in range(n):
    if not seen[i]:# 探索済みはスルー
        renketu +=1
        dfs(i)

print(renketu)

例題

連結成分の個数がわかれば解ける問題
C - Don’t be cycle

参考サイト

qiita.com

閉路検出

そのうち書きたい。

参考サイト

drken1215.hatenablog.com

木構造

木構造もグラフなんやで。

連結成分1個＆閉路なしのグラフが木構造。

頂点の深さ計測

DFSは、頂点を見つける度に関数が呼び出されるので、再帰関数の深さ＝頂点の深さになる。

import sys
sys.setrecursionlimit(10**6)

n = int(input())
tree = [[] for _ in range(n)]
parent = list(map(int, input().split()))

for i in range(n-1):
    tree[parent[i]].append(i+1)

depth = [0]*n

#深さ計測
def rec(vertex, count):
    depth[vertex] = count

    for child in tree[vertex]:
        rec(child,count+1)# 再帰の深さ＝深さ

rec(0, 0)

for ans in depth:
    print(ans)