Spiral book in Python! Python with a spiral book! (Chapter 14 ~)

This article will be updated from time to time.

Spiral book (Chapter 14-)

Please see here for the spiral book (~ 13 chapters).

Chapter 14 Advanced Data Structures

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

Worshall Floyd

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

Topological sort

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

Kruskal

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

Spiral book in Python! Python with a spiral book! (Chapter 14 ~)
Ant book with python (chapter3 intermediate edition ~)
[Python] Get the files in a folder with Python
Create a virtual environment with conda in Python
Work in a virtual environment with Python virtualenv.
Create a new page in confluence with Python
Take a screenshot in Python
How to convert / restore a string with [] in python
Scraping with selenium in Python
Create a function in Python
Create a dictionary in Python
Working with LibreOffice in Python
Scraping with chromedriver in python
Debugging with pdb in Python
Playing with a user-local artificial intelligence API in Python
Make a simple Slackbot with interactive button in python
[Let's play with Python] Make a household account book
Try embedding Python in a C ++ program with pybind11
Working with sounds in Python
Scraping with Selenium in Python
Scraping with Tor in Python
Tweet with image in Python
I want to work with a robot in python.
Make a bookmarklet in Python
A addictive point in "Bayesian inference experience with Python"
Make a fortune with Python
Combined with permutations in Python
Draw a heart in Python
Run a Python file with relative import in PyCharm
Create a directory with python
Create a fake Minecraft server in Python with Quarry
Try running python in a Django environment created with pipenv
A Python program in "A book that gently teaches difficult programming"
I made a simple typing game with tkinter in Python
Create a list in Python with all followers on twitter
Created a reading record book in conjunction with PostgreSQL in Flask
Create a child account for connect with Stripe in Python
Let's create a script that registers with Ideone.com in Python.
I made a simple book application with python + Flask ~ Introduction ~
Solve the spiral book (algorithm and data structure) with python!
I made a puzzle game (like) with Tkinter in Python
Number recognition in images with Python
Maybe in a python (original title: Maybe in Python)
[Python] What is a with statement?
Write a binary search in Python
Solve ABC163 A ~ C with Python
Operate a receipt printer with python
A python graphing manual with Matplotlib.
Testing with random numbers in Python
[python] Manage functions in a list
Hit a command in Python (Windows)
GOTO in Python with Sublime Text 3
Working with LibreOffice in Python: import
100 Language Processing Knock with Python (Chapter 1)
Create a DI Container in Python
Scraping with Selenium in Python (Basic)
100 Language Processing Knock Chapter 1 in Python
Let's make a GUI with python.
CSS parsing with cssutils in Python
Solve ABC166 A ~ D with Python
Draw a scatterplot matrix in python