Pythonで螺旋本！螺旋本でPython！（１４章〜）

この記事は随時更新していきます。

螺旋本（１４章〜）

螺旋本（〜１３章）はこちらをご覧ください。

14章 高度なデータ構造

Union Find Tree

class UnionFindTree():

    def __init__(self, n):
        #木全体の要素数
        self.n  = n
        #root[x]<0ならそのノードが根でありその値が木の要素数
        self.root = [-1] * (n+1)
        #ランク
        self.rank = [1] * (n+1)

    def find_root(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def is_same(self,x,y):
        return self.find_root(x) == self.find_root(y)

    def count_node(self,x):
        return -1 * self.root[self.find_root(x)]

上で作成したUnion find treeをimportして、螺旋本内の問題をときました。

from union_find_tree import UnionFindTree

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

uft = UnionFindTree(n)

ans = []
for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        uft.unite(x,y)
    elif com == 1:
        if uft.is_same(x,y):
            ans.append(1)
        else:
            ans.append(0)
for j in ans:
    print(j)



'''
5 12
0 1 4
0 2 3
1 1 2
1 3 4
1 1 4
1 3 2
0 1 3
1 2 4
1 3 0
0 0 4
1 0 2
1 3 0
'''

Chapter15

ワーシャルフロイド

v, e = map(int, input().split())

inf = float("inf")

#edgesをdp的に用いる
edges = [[inf]*v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, input().split())
    edges[s][t] = d

for w in range(v):
    edges[w][w] = 0

for k in range(v):
    for i in range(v):
        for j in range(v):
            edges[i][j] = min(edges[i][j], edges[i][k]+edges[k][j])


if any(edges[i][i] < 0 for i in range(v)):
    print("NEGATIVE CYCLE")
else:
    for x in edges:
        x = ["INF" if y == inf else str(y) for y in x]
        print(" ".join(x))

トポロジカルソート

こちらを参考にさせていただきました。

from collections import deque

v, e = map(int, input().split())
adj = [[] for _ in range( v)]
inflow = [0] * v
for _ in range(e):
    s, t = map(int, input().split())
    inflow[t] += 1
    adj[s].append(t)

def topological_sort(adj, inflow):
    is_visited = [False] * len(inflow)
    res = []

    def bfs(s):
        #sを始点とする
        q = deque([s])
        is_visited[s] = True
        while q:
            p = q.popleft()
            res.append(p)
            for r in adj[p]:
                inflow[r] -= 1
                if (inflow[r] == 0) and (not is_visited[r]):
                    q.append(r)
                    is_visited[r] = True

    for x in range(len(inflow)):
        if (inflow[x] == 0) and (not is_visited[x]):
            bfs(x)
    return res

for i in topological_sort(adj, inflow):
    print(i)

クラスカル

Union Find Treeを用いてクラスカル法（最小全域木のアルゴリズム）を実装するとかなり楽です。

from union_find_tree import UnionFindTree

v, e = map(int,input().split())
edges = []
for _ in range(e):
    s, t, w = map(int, input().split())
    edges.append((w, s, t))

#edgesは予めsortする
edges.sort()

def kuruskal(n, edges):
    uft = UnionFindTree(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not uft.is_same(s, t):
            res += w
            uft.unite(s, t)
    return res

print(kuruskal(v, edges))

chapter17