競プロ初中級者100問

ABC120D Decayed Bridges

この記事で使うデータ構造

Union-Find

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc120/tasks/abc120_d

この問題はUnion-Findと呼ばれるデータ構造で解くことができます。

方針

橋を削除していくのではなく、橋が全くない状態から追加していくシミュレーションを行います。

最初の不便さはN*(N-1)/2です。橋を追加するごとに、追加されることで繋がる島の群Aの島の数と群Bのそれの積を引けば良いことになります。このような集合を管理するデータ構造としてUnion-Findを利用すると良いです。

Union-Findとは

互いに素なデータ集合を管理するためのデータ構造です。
Union-Findは以下の二つの機能を持っています。

  • union 二つの集合を併合する
  • find 指定した要素がどの集合に属するかを判定する

データ構造そのものはdisjoint-setと呼び、それに対する操作をUnion-Findと呼ぶ場合もありますが、この記事ではデータ構造をUnion-Findと呼ぶことにします。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class UnionFind:
    def __init__(self, n):
        self.nodes = n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i): # どの集合に属しているか（根ノードの番号）
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j): # 二つの集合を併合
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j): # 同じ集合に属するかを判定
        return self.find(i)==self.find(j)

    def get_parents(self): # 根ノードの一覧を取得
        for n in range(self.nodes): # findで経路圧縮する
            self.find(n)
        return self.parents

    def size(self, i):
        p = self.find(i)
        return self.sizes[p]


N, M = map(int, input().split())
AB = []
B = []
for m in range(M):
    a, b = map(int, input().split())
    AB.append((a-1,b-1))

ans = []
score = N * (N-1) // 2
uf = UnionFind(N)
for a, b in AB[::-1]:
    ans.append(score)
    if not uf.same(a,b):
        score -= uf.size(a) * uf.size(b)
        uf.unite(a,b)    

for score in ans[::-1]:
    print(score)

記事情報

  • 投稿日：2020年5月19日
  • 最終更新日：2020年5月19日