Please see here for the spiral book (~ 13 chapters).
Union Find Tree
class UnionFindTree():
def __init__(self, n):
#Number of elements in the entire tree
self.n = n
#root[x]<If 0, the node is the root and its value is the number of elements in the tree
self.root = [-1] * (n+1)
#Rank
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)]
I imported the Union find tree created above and ran into a problem in the spiral book.
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")
#Use edges as 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))
[Here](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-Range-Search-kD-Tree) was used as a reference.
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):
#Starting from 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)
It is quite easy to implement the Kruskal method (minimum spanning tree algorithm) using 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 are sorted in advance
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
Recommended Posts