[Python] UnionFind ABC177D

ABC177D

There are various implementations of UnionFind, but in this question, it is very easy to solve the implementation that holds the number of nodes in the parents array. The number of nodes is held as follows.

-When it is a child, it stores the parent node number. When it is a root, it stores the number of nodes as a negative number. -When the number is negative, it is the root, and its absolute value represents the number of nodes in the tree.

Sample code


import sys

#UnionFindTree class definition
class UnionFind():
    #Class constructor
    #self is the instance itself
    def __init__(self, n):
        #Parent node-Initialize to 1
        self.parents = [-1] * n

    #Find the root
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    #Merge x and y trees
    def union(self, x, y):
        #Root search
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

#Creating a Union Find instance
uf = UnionFind(N)
for a, b in info:
    #Adjust the index, a,b join trees
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)

Recommended Posts

[Python] UnionFind ABC177D
[Python] ABC175D
[Python] DP ABC184D
Solve ABC168D in Python
Solve ABC167-D in Python
[Python] Interval scheduling ABC103D
[Python] Cumulative sum ABC186D
[Python] Binary search ABC155D
Solve ABC159-D in Python
[Python] Dynamic programming ABC015D
[Python] Cumulative sum ABC179D
[Python] BFS (breadth-first search) ABC168D
ABC161D Lunlun Number with python3
Implemented image segmentation in python (Union-Find)
[Python] How to derive nCk (ABC156-D)
kafka python
Python basics ⑤
python + lottery 6
Python Summary
Python comprehension
Python technique
Studying python
Python memorandum
Python FlowFishMaster
Python service
python tips
python function ①
Python basics
Python memo
ufo-> python (3)
Python comprehension
install python
Python Singleton
Python basics ④
Python Memorandum 2
python memo
Python Jinja2
Python increment
atCoder 173 Python
[Python] function
Python installation
python tips
Installing Python 3.4.3.
Try python
Python memo
Python iterative
Python algorithm
Python2 + word2vec
[Python] Variables
Python sys.intern ()
Python tutorial
Python decimals
python underscore
Python summary
Start python
Note: Python
Python basics ③
python log
Python basics
[Scraping] Python scraping
Python update (2.6-> 2.7)