Dieser Artikel wird von Zeit zu Zeit aktualisiert.

Spiralbuch (Kapitel 14-)

Das Spiralbuch (~ 13 Kapitel) finden Sie hier.

Kapitel 14 Erweiterte Datenstruktur

Union Find Tree

class UnionFindTree():

    def __init__(self, n):
        #Anzahl der Elemente im gesamten Baum
        self.n  = n
        #root[x]<Bei 0 ist der Knoten die Wurzel und sein Wert die Anzahl der Elemente im Baum
        self.root = [-1] * (n+1)
        #Rang
        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)]

Ich habe den oben erstellten Union-Find-Baum importiert und bin auf ein Problem im Spiralbuch gestoßen.


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

Worshall Floyd

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

inf = float("inf")

#Verwenden Sie Kanten als 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))

Topologische Sortierung

[Hier](https://aotamasaki.hatenablog.com/entry/2019/12/01/%E8%9E%BA%E6%97%8B%E6%9C%AC%E3%82%92Python%E3%81 % A7% E8% A7% A3% E3% 81% 8F_Part3 # P324-DSL_2_C-Bereichssuche-kD-Baum) wurde als Referenz verwendet.

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):
        #Ausgehend von 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)

Klasse Cal

Es ist ziemlich einfach, die Clascal-Methode (Minimum Whole Area Tree-Algorithmus) mit Union Find Tree zu implementieren.

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))

#Kanten werden im Voraus sortiert
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