最大流問題

問題

$N$ 個のタンクと $M$ 本のパイプがあります。

$j$ 本目のパイプはタンク $A_j$ からタンク $B_j$ の方向に毎秒 $C_j$ リットルまでの水を流すことができます。

タンク $1$ からタンク $N$ まで毎秒最大何リットルの水を流すことができますか。

ただし、タンクに水をためることはできません。

[制約]
🔹$ 2 \leqq N \leqq 400 $
🔹$ 1 \leqq M \leqq 4000 $
🔹$ 0 \leqq C_j \leqq 5000 $
🔹$ 答えは5000以下の整数 $

解き方

この問題は最大流問題と呼ばれる、グラフ上の最大流量を求める問題の一種です。

まず、各タンクを頂点とし、各パイプを辺とするグラフを作成します。

辺の容量はそのパイプが運べる最大の水の量 $C_j$ とします。

このグラフに対して、最大流量を求めるアルゴリズムを実行することで、タンク $1$ からタンク $N$ への最大流量を求めることができます。

有名な最大流アルゴリズムには、Ford-Fulkerson アルゴリズムや、Dinic アルゴリズムがあります。

ソースコード

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#--------- 入力例１ ----------
N = 6
M = 7
A = [1, 1, 2, 2, 3, 4, 5]
B = [2, 4, 3, 5, 6, 5, 6]
C = [5, 4, 4, 7, 3, 3, 5]
#-----------------------------

from collections import defaultdict

class FordFulkerson:
    def __init__(self, n):
        self.n = n
        self.graph = defaultdict(list)
        self.visited = [False] * n
    
    def add_edge(self, u, v, c):
        self.graph[u].append([v, c, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        self.visited[v] = True
        for i, (nv, cap, rev) in enumerate(self.graph[v]):
            if self.visited[nv] or cap == 0:
                continue
            d = self.dfs(nv, t, min(f, cap))
            if d == 0:
                continue
            self.graph[v][i][1] -= d
            self.graph[nv][rev][1] += d
            return d
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.visited = [False] * self.n
            f = self.dfs(s, t, float('inf'))
            if f == 0:
                break
            flow += f
        return flow

max_flow = FordFulkerson(N + 1)
for i in range(M):
    max_flow.add_edge(A[i], B[i], C[i])

print(max_flow.max_flow(1, N))

このソースコードは、最大フロー問題を解くためにフォード・ファルカーソン法を実装したものです。

フォード・ファルカーソン法は、エッジのフロー量を増加させることによって最大フローを求めるアルゴリズムです。

このコードでは、最大フロー問題を解くために、FordFulkersonというクラスを定義しています。

このクラスは、グラフの構造を保持するための変数graphと、最大フローを求めるための関数max_flowを持ちます。

まず、入力例１のデータに従ってグラフを構築します。

このグラフは、defaultdictを用いて辞書形式で表現されており、各頂点にはその頂点に接続するエッジ（辺）の情報が保持されています。

次に、最大フローを求めるために、dfs関数を定義しています。

この関数は、sからtへの最大フローを求めるために、深さ優先探索を実行します。

具体的には、現在の頂点から次の頂点へのパスを探索し、最大フローを更新していきます。

最後に、max_flow関数を呼び出すことで、sからtへの最大フローを求めることができます。

この関数は、whileループを用いて、dfs関数を反復的に呼び出して最大フローを求めます。

[実行結果（入力例１）]

8

入力例１の場合、タンク $1$ からタンク $N$ へ毎秒最大 $8$ リットルの水を流すことができることが分かりました。

二分グラフ判定

問題

頂点数 $n$ の無向グラフがあります。

隣接している頂点同士が違う色になるように、頂点に色を塗っていきます。

２色以内ですべての頂点を塗ることができるかどうか判定してください。

多重辺やループはないもとのします。

[制約]
🔹$ 1 \leqq N \leqq 1000 $

解き方

この問題は、二部グラフかどうかを判定する問題として知られています。

二部グラフとは、グラフを2つの部分集合に分け、同じ部分集合に属する頂点同士は隣接しないようにできるグラフのことです。

以下の手順に従って、二部グラフかどうかを判定することができます。

１．任意の頂点を1つ選び、そこからBFS（幅優先探索）またはDFS（深さ優先探索）を行います。
２．隣接する頂点のうち、まだ色を塗っていない頂点に、異なる色を塗ります。
３．2で塗られた頂点をスタートにして、再度BFSまたはDFSを行い、色を塗っていない頂点に色を塗ります。
４．2と3を繰り返し行い、すべての頂点に色を塗ることができたら、そのグラフは二部グラフであり、2色以内で塗ることができます。
　　一方、どのようにしてもすべての頂点に色を塗ることができなければ、そのグラフは二部グラフではありません。

ソースコード

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#-------- 入力例１ ---------
n = 3            # 頂点数
# 隣接リスト
adj_list = [
    (1, 2),     # 頂点0につながっている頂点のリスト
    (0, 2),     # 頂点1につながっている頂点のリスト
    (0, 1)      # 頂点2につながっている頂点のリスト
]
#-------- 入力例２ ---------
n = 4            # 頂点数
# 隣接リスト
adj_list = [
    (1, 3),     # 頂点0につながっている頂点のリスト
    (0, 2),     # 頂点1につながっている頂点のリスト
    (1, 3),     # 頂点2につながっている頂点のリスト
    (0, 2)      # 頂点3につながっている頂点のリスト
]
#---------------------------
def is_bipartite(adj_list):
    color = [-1] * len(adj_list)
    color[0] = 0
    queue = [0]
    while queue:
        v = queue.pop(0)
        for u in adj_list[v]:
            if color[u] == -1:
                color[u] = 1 - color[v]
                queue.append(u)
            elif color[u] == color[v]:
                return False
    return True

if is_bipartite(adj_list):
    print("Yes")
else:
    print("No")

このコードでは、is_bipartite関数で、グラフが二部グラフかどうかを判定しています。

具体的には、1つ目の頂点を0番目の色で塗り、BFSで隣接する頂点に異なる色を塗っていくことで、二部グラフであるかどうかを判定しています。

二部グラフである場合は、すべての頂点に色を塗ることができるので、結果として“Yes”を出力します。

一方、二部グラフでない場合は、すべての頂点に色を塗ることができないため、結果として“No”を出力します。

[実行結果（入力例１）]

No

入力例１のグラフを塗るためには３色必要となるため、解は“No”となります。

[実行結果（入力例２）]

Yes

入力例２のグラフは、２色で塗ることができるため、解は“Yes”となります。

最大全域木問題

問題

頂点数 $N$、辺数 $M$ のグラフがあります。

頂点には $1$ から $N$ までの番号が付けられており、辺 $i$ は頂点 $A_i$ と $B_i$ を双方向に結ぶ長さ $C_i$ の辺です。

このグラフの最大全域木における辺の長さの総和を求めて下さい。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq M \leqq 100000 $
🔹$ 1 \leqq C_i \leqq 10000 $
🔹このグラフは連結である。

解き方

全域木とは、$M$ 個の辺の中からいくつかを選んで作った全ての頂点が繋がっている木のことです。

全域木の中でも「長さの合計」が最大となるものを最大全域木といいます。

最大全域木は『長い辺から追加していく』という単純な貪欲法によって導き出すことができます。

ソースコード解説

前回記事では最小全域木の辺の長さの総和を求めましたが、今回の最大全域木の辺の長さの総和を求める場合は、辺の長さのソート順を逆にする変更だけで対応できます。

ソースコードの50行目だけ変更しており、辺の長い順にソートしています。

その他の処理は前回記事同様ですので、処理詳細はそちらをご参照下さい。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#-------- 入力例１ ---------
N = 7       # 頂点数
M = 9       # 辺数
# つながっている２つの頂点とその長さ
edges = [
    (1, 2, 12),
    (1, 3, 10),
    (2, 6, 160),
    (2, 7, 15),
    (3, 4, 1),
    (3, 5, 4),
    (4, 5, 3),
    (4, 6, 120),
    (6, 7, 14)
]
#---------------------------
# Union-Find 木
class unionfind:
    # n 頂点の Union-Find 木を作成
    def __init__(self, n):
        self.n = n
        self.par = [ -1 ] * (n + 1) # 最初は親が無い
        self.size = [ 1 ] * (n + 1) # 最初はグループの頂点数が 1
    
    # 頂点 x の根を返す関数
    def root(self, x):
        # 1 個先（親）がなくなるまで進み続ける
        while self.par[x] != -1:
            x = self.par[x]
        return x
    
    # 要素 u, v を統合する関数
    def unite(self, u, v):
        rootu = self.root(u)
        rootv = self.root(v)
        if rootu != rootv:
            # u と v が異なるグループのときのみ処理を行う
            if self.size[rootu] < self.size[rootv]:
                self.par[rootu] = rootv
                self.size[rootv] += self.size[rootu]
            else:
                self.par[rootv] = rootu
                self.size[rootu] += self.size[rootv]
    
    #  要素 u と v が同一のグループかどうかを返す関数
    def same(self, u, v):
        return self.root(u) == self.root(v)

# 辺を長さの大きい順にソート
edges.sort(key = lambda x: -x[2])

# 最小全域木を求める
uf = unionfind(N)
answer = 0
for a, b, c in edges:
    if not uf.same(a, b):
        uf.unite(a, b)
        answer += c

# 答えの出力
print('解：', answer)

[実行結果（入力例１）]

解： 321

最大全域木における辺の長さの総和を求めることができました。

最小全域木問題

問題

頂点数 $N$、辺数 $M$ のグラフがあります。

頂点には $1$ から $N$ までの番号が付けられており、辺 $i$ は頂点 $A_i$ と $B_i$ を双方向に結ぶ長さ $C_i$ の辺です。

このグラフの最小全域木における辺の長さの総和を求めて下さい。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq M \leqq 100000 $
🔹$ 1 \leqq C_i \leqq 10000 $
🔹このグラフは連結である。

解き方

全域木とは、$M$ 個の辺の中からいくつかを選んで作った全ての頂点が繋がっている木のことです。

全域木の中でも「長さの合計」が最小となるものを最小全域木といいます。

最小全域木は『短い辺から追加していく』という単純な貪欲法によって導き出すことができます。

この方法はクラスカル法と呼ばれており、配列のソートとUnion-Find木を使って実装することができます。

ソースコード解説

下記のソースコードは、Union-Find 木を使って与えられたグラフの連結成分を管理し、クエリーを処理するプログラムです。

入力例１では、3つの頂点と4つのクエリーが与えられています。

クエリー１は頂点同士を結ぶ辺を追加し、クエリー２は２つの頂点が同じ連結成分に属するかを判定するものです。

まず、Union-Find 木のクラスを定義しています。

コンストラクタでは、頂点数 n を受け取り、par と size の初期化を行っています。

par は親の頂点を保持する配列で、初期値は全て -1 です。

size はグループの頂点数を保持する配列で、初期値は全て 1 です。

次に、root 関数では、引数で指定された頂点 x の根を探索して返します。

par[x] が -1 になるまで、頂点 x の親に移動していきます。

unite 関数は、引数で指定された要素 u, v を同一のグループに統合します。

この関数内では、それぞれの根を取得し、もし根が異なる場合はグループの頂点数が小さい方を大きい方に統合します。

par 配列には親の頂点を、size 配列にはグループの頂点数を記録しています。

same 関数は、引数で指定された要素 u, v が同一のグループに属するかどうかを判定します。

この関数内では、root 関数を呼び出して u, v の根を比較します。

次にクエリーの処理を行います。

クエリー１の場合は、union 関数を呼び出して頂点 u, v を統合します。

クエリー２の場合は、same 関数を呼び出して頂点 u, v が同一のグループに属するかどうかを判定します。

最後に最小全域木における辺の長さの総和を出力しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#-------- 入力例１ ---------
N = 7       # 頂点数
M = 9       # 辺数
# つながっている２つの頂点とその長さ
edges = [
    (1, 2, 12),
    (1, 3, 10),
    (2, 6, 160),
    (2, 7, 15),
    (3, 4, 1),
    (3, 5, 4),
    (4, 5, 3),
    (4, 6, 120),
    (6, 7, 14)
]
#---------------------------
# Union-Find 木
class unionfind:
    # n 頂点の Union-Find 木を作成
    def __init__(self, n):
        self.n = n
        self.par = [ -1 ] * (n + 1) # 最初は親が無い
        self.size = [ 1 ] * (n + 1) # 最初はグループの頂点数が 1
    
    # 頂点 x の根を返す関数
    def root(self, x):
        # 1 個先（親）がなくなるまで進み続ける
        while self.par[x] != -1:
            x = self.par[x]
        return x
    
    # 要素 u, v を統合する関数
    def unite(self, u, v):
        rootu = self.root(u)
        rootv = self.root(v)
        if rootu != rootv:
            # u と v が異なるグループのときのみ処理を行う
            if self.size[rootu] < self.size[rootv]:
                self.par[rootu] = rootv
                self.size[rootv] += self.size[rootu]
            else:
                self.par[rootv] = rootu
                self.size[rootu] += self.size[rootv]
    
    #  要素 u と v が同一のグループかどうかを返す関数
    def same(self, u, v):
        return self.root(u) == self.root(v)

# 辺を長さの小さい順にソート
edges.sort(key = lambda x: x[2])

# 最小全域木を求める
uf = unionfind(N)
answer = 0
for a, b, c in edges:
    if not uf.same(a, b):
        uf.unite(a, b)
        answer += c

# 答えの出力
print('解：', answer)

[実行結果（入力例１）]

解： 55

最小全域木における辺の長さの総和を求めることができました。

Union-Find木②

問題

ある地域には $N$ 個の駅と $M$ 本の鉄道路線があります。

駅には $1$ から $N$ までの番号が付けられていて、$i$ 本目の路線は駅 $A_i$ と駅 $B_i$ を双方向に結んでいます。

この地域に台風が上陸すると、いくつかの路線は運休になってしまいます。

以下のようなクエリ―が $Q$ 個与えられるのでそのクエリ―を処理してください。

　クエリー１：$x$ 本目の路線が運休になる。
　クエリー２：運休状況を踏まえて駅 $s$ から駅 $t$ へ移動できるかどうかを答える。

解き方・ソースコード

この問題も前回記事同様、Union-Find木を使って解いていきますが、辺を減らしながらの連結状況を答えるのは難しいので、クエリーを逆向きにして辺を増やしながら処理することにします。

まずソースコードの冒頭では、次のように入力データを設定しています。

　・N： 頂点の数（駅の数）。
　・M： 辺の数（２つの駅を結ぶ路線の数）。
　・edges： 辺のリスト。各要素は、頂点の番号のペアで表される。
　・Q： クエリ―の数。
　・query： クエリ―のリスト。各要素は、1または2の数字と、いくつかの頂点の番号の組み合わせで構成される。

このプログラムは、以下のような処理を行います。

　１．辺のリストをインデックス0から始まるように修正する。
　２．クエリ―に応じて、最後まで残っている辺のリストを取得する。
　３．Union-Find木を用いて、最後まで残っている辺でグラフを構成する。
　４．クエリ―を逆順に処理し、連結を増やしながら移動可能かどうかの回答を求める。
　５．回答を出力する。

Union-Find木を使ってグラフを構成していきます。

Union-Find木は、グループを管理するためのデータ構造です。

各要素は、自身が属するグループの根の番号を覚えています。

グループをマージするときには、根の番号を統一します。

これによって、任意の2つの要素が同じグループに属するかどうかを簡単に判定することができます。

このプログラムは、最後まで残っている辺でグラフを構成します。

そして、クエリ―を逆順に処理しながら、Union-Find木を使ってグループをマージしていきます。

最後に、各クエリ―に対する回答を出力します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#-------- 入力例１ ---------
N = 5       # 駅の数
M = 5       # ２つの駅をつなぐ路線の数
edges = [
    (1, 2),
    (2, 3),
    (3, 4),
    (4, 5),
    (3, 5)
]

Q = 5       # クエリ―数
query = [
    [2, 1, 5],
    [1, 3],
    [2, 1, 5],
    [1, 5],
    [2, 1, 5]
]
#---------------------------
edge = []
# インデックスを0スタートにする
for A, B in edges:
    edge.append((A - 1, B - 1))

# 最後まで残っている辺を求める
last = [True] * M
for q in query:
    if q[0] == 1:
        q[1] -= 1
        last[q[1]] = False
    else:
        q[1] -= 1
        q[2] -= 1

# union-find木
uf = [-1] * N
def root(i):
    while True:
        if uf[i] < 0:
            return i
        if uf[uf[i]] < 0:
            return uf[i]
        uf[i] = uf[uf[i]]
        i = uf[i]

def unite(i, j):
    i = root(i)
    j = root(j)
    if i == j:
        return
    # union by size
    if uf[i] > uf[j]:
        i, j = j, i
    uf[i] += uf[j]
    uf[j] = i

ans = []
for i in range(M):
    if last[i]:
        A, B = edge[i]
        unite(A, B)

# クエリ―を逆順に処理する
for q in reversed(query):
    if q[0] == 1:
        A, B = edge[q[1]]
        unite(A, B)
    else:
        _, U, V = q
        ans.append("移動可能" if root(U) == root(V) else "移動不可")

# クエリ―の順番を戻して、回答を表示
for s in reversed(ans):
    print(s)

[実行結果（入力例１）]

移動可能

移動可能

移動不可

クエリ―に応じて、駅間の移動ができるかどうかを出力することができました。

Union-Find木

問題

頂点数 $N$ のグラフに対して、次の２種類のクエリーを処理してください。

　クエリー１：頂点 $u$ と頂点 $v$ を双方向に結ぶ辺を追加する。
　クエリー２：頂点 $u$ と頂点 $v$ は同じ連結成分に属するかを答える。

最初はグラフに辺が一本もなく、与えられるクエリ―の数は $Q$ 個であるとします。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq Q \leqq 100000 $

解き方・ソースコード

この問題は、Union-Find木というデータ構造を使って解くことができます。

Union-Fin木dとは、グループ分けを効率的に管理することができるデータ構造です。

次のような２種類のクエリ―を高速に処理することができます。

🔹統合クエリー：要素 $u$ を含むグループと、要素 $v$ を含むグループを統合する。
🔹回答クエリー：要素 $u$ と 要素 $v$ が同じグループにあるかどうかを判定する。

以下のソースコードは、Union-Find木を使って与えられたグラフの連結成分を管理し、クエリーを処理します。

入力例１として、3つの頂点と4つのクエリーを設定しています。

クエリー１は頂点1と頂点2を結ぶ辺を追加し、クエリー２は頂点2と頂点3が同じ連結成分に属するかを判定するものです。

まず、Union-Find木のクラスを定義します。

コンストラクタでは、頂点数 n を受け取り、par と size の初期化を行っています。

par は親の頂点を保持する配列で、初期値は全て -1 です。

size はグループの頂点数を保持する配列で、初期値は全て 1 です。

次に、root関数では、引数で指定された頂点 x の根を探索して返します。

par[x] が -1 になるまで、頂点 x の親に移動していきます。

unite関数は、引数で指定された要素 u, v を同一のグループに統合します。

まず、それぞれの根を取得します。

もし根が異なる場合は、グループの頂点数が小さい方を大きい方に統合します。

par 配列には親の頂点を、size 配列にはグループの頂点数を記録しています。

same 関数は、引数で指定された要素 u, v が同一のグループに属するかどうかを判定します。

関数内ではroot 関数を呼び出して u, v の根を比較します。

最後に、クエリーの処理を行います。

クエリー１の場合は、union 関数を呼び出して頂点 u, v を統合します。

クエリー２の場合は、same 関数を呼び出して頂点 u, v が同一のグループに属するかどうかを判定し、結果に応じてメッセージを出力します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#-------- 入力例１ ---------
N = 3       # 頂点数
Q = 4       # クエリ―数
queries = [
    (1, 1, 2),
    (2, 1, 3),
    (1, 2, 3),
    (2, 2, 3)
]
#---------------------------
# Union-Find 木
class unionfind:
    # n 頂点の Union-Find 木を作成
    # 頂点番号が 1 - indexed になるように実装するので n + 1 としている。
    def __init__(self, n):
        self.n = n
        self.par = [ -1 ] * (n + 1) # 最初は親が無い
        self.size = [ 1 ] * (n + 1) # 最初はグループの頂点数が 1

    # 頂点 x の根を返す関数
    def root(self, x):
        # 1 個先（親）がなくなるまで、1 個先（親）に進み続ける
        while self.par[x] != -1:
            x = self.par[x]
        return x

    # 要素 u, v を統合する関数
    def unite(self, u, v):
        rootu = self.root(u)
        rootv = self.root(v)
        if rootu != rootv:
            # u と v が異なるグループのときに処理を行う
            if self.size[rootu] < self.size[rootv]:
                self.par[rootu] = rootv
                self.size[rootv] += self.size[rootu]
            else:
                self.par[rootv] = rootu
                self.size[rootu] += self.size[rootv]

    #  要素 u と v が同一のグループかどうかを返す関数
    def same(self, u, v):
        return self.root(u) == self.root(v)

# クエリの処理
uf = unionfind(N)
for tp, u, v in queries:
    if tp == 1:         # クエリ―１の処理を行う
        uf.unite(u, v)
    if tp == 2:         # クエリ―２の処理を行う
        if uf.same(u, v):
            print(f'頂点 {u} と頂点 {v} は同じ連結成分に属する。')
        else:
            print(f'頂点 {u} と頂点 {v} は同じ連結成分に属さない。')

[実行結果（入力例１）]

頂点 1 と頂点 3 は同じ連結成分に属しない。

頂点 2 と頂点 3 は同じ連結成分に属する。

クエリ―１で頂点またはそのグループを結合し、クエリ―２の回答として各頂点が同じグループに属するかどうかを判定することができました。

深さ優先探索（社員の階級）

問題

ある会社には、$N(\leqq 100000)$ 人の社員がいて、$1$ から $N$ までの番号が付けれらています。

この会社について、次の $N-1$ 個の情報が分かっています。

$i$ 個目の情報：社員 $ A_i$ と社員 $B_i$ は直属の上司と部下の関係にあり、社員 $ A_i$ と社員 $B_i$ のどちらが上司なのかは分かっていません。

社員 $T$ が社長であり、それ以外の $N-1$ 人全員が誰か1人の直属の部下であるとき各社員の階級を求めて下さい。

ただし、部下がいない社員の階級は $0$ であり、部下がいる社員の階級は、直属の部下における階級の最大値に $1$ を足した値であるとします。

解き方・ソースコード

前回記事の問題とは違い、今回の問題は社員番号の制約がないので、深さ優先探索を使って解いていきます。

まず入力値として、変数 $N$ には社員数、変数 $T$ には社長の社員番号、変数 $R$ には上司または部下の関係を設定します。

次に、階層構造を持つデータを扱うため、グラフの形式で社員の関係を表現します。

変数 $g$ には社員の関係を格納するために、空のリストで初期化し、上司・部下関係の情報をもとに関係を追加していきます。

その後、階級を格納するために配列 $rank$ を作成します。初期値はすべて0です。

関数dfsは、深さ優先探索アルゴリズムを用いて、各社員の階級を計算します。

引数 parentには、ある社員の上司の社員番号を設定します。

引数 iには、チェックする社員の社員番号を設定します。

この関数内では $dfs(i, j) + 1$により、部下の階級から自分の階級を計算しています。

そして、現在保持している階級よりも大きければ更新します。

最初の関数dfsの呼び出しは、社長の階級を求めるために $dfs(-1, T - 1)$とします。

最後に、すべての $rank$ の値を出力することで、各社員の階級を表示します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#-------- 入力例１ ---------
N = 7       # 社員数
T = 3       # 社長の社員番号
R = [(3, 2), (3, 1), (2, 5), (1, 4), (4, 6), (4, 7)]  # 上司または部下の関係 
#-------- 入力例２ ---------
# N = 7       # 社員数
# T = 7       # 社長の社員番号
# R = [(3, 2), (3, 1), (2, 5), (1, 4), (4, 6), (4, 7)]  # 上司または部下の関係 
#---------------------------
g = [[] for i in range(N)]
for A, B in R:
    A -= 1
    B -= 1
    g[A].append(B)
    g[B].append(A)

rank = [0] * N

# 深さ優先探索
#   parent:上司の社員番号
#   i:チェックする社員番号
def dfs(parent, i):
    for j in g[i]:          # ある社員の部下全員分をループ
        if j == parent:     # 上司の社員番号は無視
            continue
        r = dfs(i, j) + 1   # チェックする社員番号を上司として、その部下のランクを取得する
        if rank[i] < r:     # 現在保持しているものよりランクが大きければ更新する
            rank[i] = r
    return rank[i]
dfs(-1, T - 1)  # 上司はいないので-1、社長番号T（インデックス化するため-1）としてランクを取得する

for i in range(N):
    print(f'社員 {i + 1} の階級は {rank[i]}')

[実行結果（入力例１）]

社員 1 の階級は 2

社員 2 の階級は 1

社員 3 の階級は 3

社員 4 の階級は 1

社員 5 の階級は 0

社員 6 の階級は 0

社員 7 の階級は 0

[実行結果（入力例２）]

社員 1 の階級は 3

社員 2 の階級は 1

社員 3 の階級は 2

社員 4 の階級は 4

社員 5 の階級は 0

社員 6 の階級は 0

社員 7 の階級は 5

各社員の階級を表示することができました。

動的計画法（部下の人数）

問題

ある会社には $ N $ 人の社員がいて、地位順に $1$ から $N$ までの番号が付けられています。

社長（社員番号 $1$）以外には直属の上司が１人いて、社員 $i$ の直属の上司は社員 $A_i$ です。

各社員について、部下が何人いるかを出力してください。

ただし、社員 $y$ が社員 $x$ の部下であることは、$ x \neq y$ であり、なおかつ社員 $y$ の直属の上司をたどって社員 $x$ に到達できることを意味します。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq A_i \leqq i-1 (2 \leqq i \leqq N) $

解き方・ソースコード

動的計画法を使って、この問題を解いていきます。

まず、社員の数 $N$ と直属の上司のリスト $A$ を定義します。

次に、隣接リスト G を作成します。

隣接リストは、それぞれの社員が持つ部下の社員番号を管理します。

具体的には、社員 $i$ の持つ部下の社員番号が $j_1, j_2, \ldots, j_k$ である場合、$G[i]$ には $[j_1, j_2, \ldots, j_k]$ というリストが格納されます。

次に、動的計画法を用いて各社員が持つ部下の数を求めます。

具体的には、各社員の持つ部下の数を $dp$ というリストに保存します。

最初は全員が部下を持たないものとして、全ての要素を $0$ に初期化しています。

そして、社員 $i$ の持つ部下の数を計算するために、G[i] の要素（つまり社員 $i$ の部下の社員番号）を順番に取り出して、その社員が持つ部下の数を dp から参照して加算します。

最後に、$dp[i]$ に $1$ を加えることで、社員 $i$ の直属の部下の数を $dp$ に追加しています。

この処理を、社員 $i$ が社長（社員番号１）である場合まで繰り返します。

最後に、$dp$ の各要素を順番に出力することで、各社員が何人の部下を持つかを表示します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#-------- 入力例１ ---------
N = 7                   # 社員数
A = [1, 1, 3, 2, 4, 5]  # 社員番号２から社員番号７の直属の上司の社員番号
#---------------------------
# 隣接リストの作成
G = [list() for i in range(N + 1)]
for i in range(2, N + 1):
    G[A[i - 2]].append(i) # 上司 → 部下の方向に方向に辺を追加

# 動的計画法（dp[x] は社員 x の部下の数）
dp = [0] * (N + 1)
for i in range(N, 0, -1):
    for j in G[i]:
        dp[i] += (dp[j] + 1)

for i in range(1, N + 1):
    print(f'社員 {i} の部下の数は {dp[i]} 人')

[実行結果（入力例１）]

社員 1 の部下の数は 6 人

社員 2 の部下の数は 2 人

社員 3 の部下の数は 2 人

社員 4 の部下の数は 1 人

社員 5 の部下の数は 1 人

社員 6 の部下の数は 0 人

社員 7 の部下の数は 0 人

各社員について、部下が何人いるかを出力することができました。

ダイクストラ法②（最短経路）

問題

次のような重み付き無向グラフが与えられます。

🔹頂点数は $N$、辺の数は $M$ です。
🔹$i$ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結び、長さは $ C_i $ です。

頂点 $1$ から頂点 $N$ までの具体的な最短経路を１つ出力して下さい。

解き方・ソースコード

前回記事では、グラフにおける最短経路長を求めましたが、今回は最短経路（道筋）を求めます。

まず、与えられた辺の情報を使ってグラフを表現するために、隣接リスト g を作成します。このリストは、各頂点につながる辺の情報を保持するために使用されます。

次に、最短経路を求めるための初期化を行います。

ここでは、距離を表す cost リストと、最短経路の復元に使用する back リストを作成し、それぞれ無限大と -1 で初期化します。

また、探索を行うためのキュー q を作成し、スタート地点となる頂点の情報をキューに追加します。

その後、以下の処理をキューが空になるまで繰り返します。

1. キューから距離が最小の頂点を取り出す。
2. 取り出した頂点に隣接する頂点について、距離を更新する必要がある場合は、push 関数を呼び出して距離を更新し、キューに頂点の情報を追加する。

この push 関数は、最短経路探索中に頂点に訪れる部分を関数化したものです。

この関数では、新たな頂点に到達した場合に距離を更新し、その頂点を探索するためにキューに情報を追加します。

最短経路探索が終了したら、back リストを使って、スタート地点から終点までの最短経路を復元します。

最後に、求めた最短経路を順番に出力します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#-------- 入力例１ ---------
N = 6       # 頂点数
M = 7       # 辺の数
# つながっている頂点とその距離
edges = [
    (1, 2, 14),
    (1, 4, 22),
    (2, 3, 62),
    (2, 5, 5),
    (3, 6, 52),
    (4, 5, 38),
    (5, 6, 18)
]
#---------------------------
from heapq import heappush, heappop

g = [[] for _ in range(N)]
for A, B, C in edges:
    A -= 1
    B -= 1
    g[A].append((B, C))
    g[B].append((A, C))

INF = 1 << 61
cost = [INF] * N
back = [-1] * N
q = []

# 頂点に訪れる部分を関数化
def push(prev, i, c):
    if cost[i] <= c:
        return
    cost[i] = c
    back[i] = prev
    heappush(q, (c, i))

# 復元の都合上後ろから ダイクストラ法を行う
push(-1, N - 1, 0)
while q:
    c, x = heappop(q)
    if cost[x] != c:
        continue # 同じ頂点から複数回探索しない
    for j, d in g[x]:
        push(x, j, c + d)

# 最短経路を復元
ans = [0]
while ans[-1] != N - 1:
    ans.append(back[ans[-1]])

for x in ans:
    print(x + 1)

[実行結果（入力例１）]

1

2

5

6

最短経路（道筋）は【頂点１➡頂点２➡頂点５➡頂点６】であることが確認できました。

ダイクストラ法①（最短経路長）

問題

次のような重み付き無向グラフが与えられます。

🔹頂点数は $N$、辺の数は $M$ です。
🔹$i$ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結び、長さは $ C_i $ です。

このグラフに対して最短経路長を求めて下さい。

出力形式として、各頂点への最短距離を頂点 $1$ から頂点 $N$ まで順番に出力して下さい。

移動できない頂点の場合は、$-1$ を出力してください

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq M \leqq min(100000,N(N-1))/2 $
🔹$ 1 \leqq A_i < B_i \leqq N $
🔹$ 1 \leqq C_i \leqq 10000 $

解き方・ソースコード

ダイクストラ法を使ってこの問題を解いていきます。

ソースコードの冒頭で、グラフの情報を設定しています。

ここでは、頂点数、辺の数、および各辺の情報をタプルとしてリストに格納しています。

次に、隣接リストを作成しています。

このようにしておくことで、後続の処理で各頂点からつながっている辺を効率的に参照できるようになります。

また、このコードではPythonの組み込みモジュールheapqを使って優先度付きキューを実装しています。

これにより、次に探索すべき頂点を常に距離の短い順に処理することができます。

ダイクストラ法の実装部分では、優先度付きキューから取り出した要素が確定済みの頂点(kakutei変数)である場合はスキップしています。

また、確定していない隣接頂点について、現在の距離よりも短い経路が存在する場合は、その距離を更新し、優先度付きキューに加えます。

この処理を、優先度付きキューが空になるまで繰り返します。

最後に、各頂点までの最短距離を出力しています。

頂点までの最短距離が存在しない場合は-1を出力するようにしています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#-------- 入力例１ ---------
N = 6       # 頂点数
M = 7       # 辺の数
# つながっている頂点とその距離
edges = [
    (1, 2, 14),
    (1, 4, 22),
    (2, 3, 62),
    (2, 5, 5),
    (3, 6, 52),
    (4, 5, 38),
    (5, 6, 18)
]
#---------------------------
import heapq

# 隣接リストの作成
# 重み付きグラフなので、各辺について (隣接頂点, 重み) のタプルを記録
G = [list() for i in range(N + 1)]
for a, b, c in edges:
    G[a].append((b, c))
    G[b].append((a, c))

# 配列・キューの初期化
# キューには (距離, 頂点番号) のタプルを記録
kakutei = [ False ] * (N + 1)
cur = [float('inf')] * (N + 1)  # 距離の暫定値
cur[1] = 0
Q = []
heapq.heappush(Q, (cur[1], 1))

# ダイクストラ法
while len(Q) > 0:
    # 次に確定させるべき頂点を求める
    # 優先度付きキュー Q の最小要素を取り除き、その要素の 2 番目の値（頂点番号）を pos に代入
    pos = heapq.heappop(Q)[1]

    # Q の最小要素が「既に確定した頂点」の場合
    if kakutei[pos] == True:
        continue

    # 暫定値 cur[x] の値を更新する
    kakutei[pos] = True
    for e in G[pos]:
        # pos = e[0], cost = e[1] で対応
        if cur[e[0]] > cur[pos] + e[1]:
            cur[e[0]] = cur[pos] + e[1]
            heapq.heappush(Q, (cur[e[0]], e[0]))

# 答えを出力
for i in range(1, N + 1):
    if cur[i] == float('inf'):
        print('頂点 {} までの最短距離 {}'.format(i, -1))
    else:
        print('頂点 {} までの最短距離 {}'.format(i, cur[i]))

[実行結果（入力例１）]

頂点 1 までの最短距離 0

頂点 2 までの最短距離 14

頂点 3 までの最短距離 76

頂点 4 までの最短距離 22

頂点 5 までの最短距離 19

頂点 6 までの最短距離 37

各頂点への最短距離を求めることができました。