Partition Refinement
(data-structure/partition_refinement.hpp)

• View this file on GitHub
• Last update: 2023-03-09 17:45:18+09:00
• Include: #include "data-structure/partition_refinement.hpp"

Description

Partition refinement は，素集合を管理するデータ構造である．Union find が集合の併合を処理するのに対し，partition refinement は集合の分割を処理する．

DFA 最小化などに用いられる．

空間計算量: $O(n)$

Operations

• PartitionRefinement(int n)
  • 集合を ${0,1,\dots, n-1}$ で初期化する．
  • 時間計算量: $O(n)$
• int find(int x)
  • $x$ が属する集合の番号を返す
  • 時間計算量: $O(1)$
• bool same(int x, int y)
  • $x$ と $y$ が同じ集合に属するかを判定する
  • 時間計算量: $O(1)$
• int size(int i)
  • 集合 $i$ の要素数を返す
  • 時間計算量: $O(1)$
• vector<int> members(int i)
  • 集合 $i$ の要素のリストを返す
  • 時間計算量: $O(\vert S_i \vert)$
• vector<pair<int, int>> refine(vector<int> pivot)
  • 与えられたピボット $P$ を用いて，各集合 $S_i$ を $S_i \cap P$ と $S_i - P$ に分割する．
  • 分割された集合の番号を返す
  • 時間計算量: $O(\vert P \vert \log n)$

Note

Refine 操作は $O(\vert P \vert)$ でできるが，実装が面倒なので log をつけている．

DFA 最小化では，集合が分割されたときに要素数が小さい方に注目して，それに遷移してくる集合をさらに分割するということを繰り返す．計算量は，逆マージテクの要領で解析でき，遷移の数を $m$ として $O(m \log^2 n)$ (refine 操作を線形時間で行えば $O(m \log n)$) となる．

Reference

• Partition refinement - TryAlgo
• DFA minimization - Wikpedia
• verify: https://atcoder.jp/contests/tupc2022/submissions/39481650

Required by

• Chordal Graph Recognition (graph/chordal_graph_recognition.hpp)
• Lexicographic BFS (graph/lex_bfs.hpp)

Verified with

• test/yosupo/chordal_graph_recognition.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <map>
#include <set>
#include <vector>

class PartitionRefinement {
   public:
    PartitionRefinement() = default;
    explicit PartitionRefinement(int n) : sets(1), cls(n, 0) {
        for (int i = 0; i < n; ++i) sets[0].insert(i);
    }

    int find(int x) const { return cls[x]; }

    bool same(int x, int y) const {
        int cx = find(x), cy = find(y);
        return cx != -1 && cy != -1 && cx == cy;
    }

    bool contains(int x) const { return cls[x] != -1; }

    void erase(int x) {
        if (contains(x)) {
            sets[cls[x]].erase(x);
            cls[x] = -1;
        }
    }

    int size(int i) const { return sets[i].size(); }

    int member(int i) const {
        assert(0 <= i && i < (int)sets.size());
        return *sets[i].begin();
    }

    std::vector<int> members(int i) const {
        assert(0 <= i && i < (int)sets.size());
        return std::vector<int>(sets[i].begin(), sets[i].end());
    }

    std::vector<std::pair<int, int>> refine(const std::vector<int>& pivot) {
        std::map<int, std::vector<int>> split;
        for (auto x : pivot) {
            if (!contains(x)) continue;
            int i = cls[x];
            split[i].push_back(x);
            sets[i].erase(x);
        }
        std::vector<std::pair<int, int>> updated;
        for (auto& [i, s] : split) {
            int ni = sets.size();
            sets.emplace_back(s.begin(), s.end());
            if (sets[i].size() < sets[ni].size()) {
                std::swap(sets[i], sets[ni]);
            }
            if (sets[ni].empty()) {
                sets.pop_back();
                continue;
            }
            for (auto x : sets[ni]) {
                cls[x] = ni;
            }
            updated.push_back({i, ni});
        }
        return updated;
    }

   private:
    std::vector<std::set<int>> sets;
    std::vector<int> cls;
};

#line 2 "data-structure/partition_refinement.hpp"
#include <algorithm>
#include <cassert>
#include <map>
#include <set>
#include <vector>

class PartitionRefinement {
   public:
    PartitionRefinement() = default;
    explicit PartitionRefinement(int n) : sets(1), cls(n, 0) {
        for (int i = 0; i < n; ++i) sets[0].insert(i);
    }

    int find(int x) const { return cls[x]; }

    bool same(int x, int y) const {
        int cx = find(x), cy = find(y);
        return cx != -1 && cy != -1 && cx == cy;
    }

    bool contains(int x) const { return cls[x] != -1; }

    void erase(int x) {
        if (contains(x)) {
            sets[cls[x]].erase(x);
            cls[x] = -1;
        }
    }

    int size(int i) const { return sets[i].size(); }

    int member(int i) const {
        assert(0 <= i && i < (int)sets.size());
        return *sets[i].begin();
    }

    std::vector<int> members(int i) const {
        assert(0 <= i && i < (int)sets.size());
        return std::vector<int>(sets[i].begin(), sets[i].end());
    }

    std::vector<std::pair<int, int>> refine(const std::vector<int>& pivot) {
        std::map<int, std::vector<int>> split;
        for (auto x : pivot) {
            if (!contains(x)) continue;
            int i = cls[x];
            split[i].push_back(x);
            sets[i].erase(x);
        }
        std::vector<std::pair<int, int>> updated;
        for (auto& [i, s] : split) {
            int ni = sets.size();
            sets.emplace_back(s.begin(), s.end());
            if (sets[i].size() < sets[ni].size()) {
                std::swap(sets[i], sets[ni]);
            }
            if (sets[ni].empty()) {
                sets.pop_back();
                continue;
            }
            for (auto x : sets[ni]) {
                cls[x] = ni;
            }
            updated.push_back({i, ni});
        }
        return updated;
    }

   private:
    std::vector<std::set<int>> sets;
    std::vector<int> cls;
};

Back to top page