【アルゴリズム向上クラス】そして調査集

併合調査集に関する問題は少なくないが、公式に与えられたデータは30件(2020-02-20現在)であるが、 のラベルが貼られていない問題もあるが、使用して調査集するのは確かに簡単である.このような問題がテンプレートをマスターすれば、このような問題をブラシするのは非常に速く、間違いを犯す確率が大幅に低下します.これがテンプレートのメリットです.
私はここでいくつかの問題をまとめ、調査しました.

547.モーメンツ

721.口座合併

990.等式方程式の満足性

皆さんはテンプレートを習ってから上の3つの問題を使ってもいいです.できないのは私の問題解を見てもいいです.
調査セットの概要
アルゴリズムを調べ,主に図論における「動的連通性」問題を解決する.
Union-Findアルゴリズムは図の動的連通性の問題を解決して、このアルゴリズム自体は難しくなくて、応用できるかどうかは主にあなたの抽象的な問題の能力を見て、原始的な問題を抽象的に図論に関する問題にすることができるかどうかです.
このアルゴリズムがよく分からない場合は、この文章Union-Findアルゴリズムの詳細を見て、非常に詳しく説明することをお勧めします.
収集された要素を部門の人と見なすことができ、何人かが1つの部門の数を構成することができます.
コアを収集する3つの方法は、それぞれunion、find、connectedである.

union:2人が所属する2つの部門を1つの部門に統合する(2人が同じ部門であれば、実際の山は統合する必要はない)

(図はlabuladongから)

find:ある人の部門を検索leader

connnected:二人が一つの部門かどうかを判断する

(図はlabuladongから)
かたわく
これは私がよく使うテンプレートで、具体的なテーマによって細かい変化をしますが、大体変わりません.

class UF:
    parent = {}
    cnt = 0
    def __init__(self, M):
        #     parent   cnt

    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]
        return x
    def union(self, p, q):
        if self.connected(p, q): return
        self.parent[self.find(p)] = self.find(q)
        self.cnt -= 1
    def connected(self, p, q):
        return self.find(p) == self.find(q)

パフォーマンスを向上させるには、このテンプレートが適しており、コードが少し複雑です.

class UF:
    parent = {}
    size = {}
    cnt = 0
    def __init__(self, M):
        #     parent，size   cnt

    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]
            #     
            self.parent[x] = self.parent[self.parent[x]];
        return x
    def union(self, p, q):
        if self.connected(p, q): return
        #          ，       
        leader_p = self.find(p)
        leader_q = self.find(q)
        if self.size[leader_p] < self.size[leader_q]:
            self.parent[leader_p] = leader_q
        else:
            self.parent[leader_q] = leader_p
        self.cnt -= 1
    def connected(self, p, q):
        return self.find(p) == self.find(q)

状況に応じて異なるテンプレートを使用することができます.