lib/graph/rooted_tree_topological_order_with_minimum_inversions.hpp

• View this file on GitHub
• Last update: 2025-05-17 03:39:23+09:00
• Include: #include "lib/graph/rooted_tree_topological_order_with_minimum_inversions.hpp"

Depends on

• Eraseable Priority Queue (削除可能優先度付きキュー) (lib/data_structure/priority_queue.hpp)
• Union-Find (lib/data_structure/union_find.hpp)

Verified with

• test/library_checker/tree/rooted_tree_topological_order_with_minimum_inversions.test.cpp

Code

#pragma once

#include <iostream>
#include <vector>
#include <queue>
#include "../data_structure/union_find.hpp"
#include "../data_structure/priority_queue.hpp"

template <typename T>
struct fraction{
    T p, q; // long long or BigInt
    fraction(T P = 0, T Q = 1) : p(P), q(Q){}
    inline bool operator==(const fraction &other) const {
        return p * other.q == other.p * q;
    }
    inline bool operator<(const fraction &other) const {
        if(other.p == 0 && other.q == 0) return false;
        if(p == 0 && q == 0) return true;
        return p * other.q < other.p * q;
    }
};

template <typename T>
std::pair<T, std::vector<int>> rootedTreeTopologicalOrderWithMinimumInversions(const std::vector<int> &par, const std::vector<T> &zero, const std::vector<T> &one){
    std::vector<int> G = par;
    int n = G.size();
    UnionFind uf(n);
    PriorityQueue<std::pair<fraction<T>, int>> pq;
    std::vector<T> inv(n);
    std::vector<fraction<T>> fv(n);
    std::vector<std::deque<int>> p(n);
    for(int i = 0; i < n; ++i){
        fv[i] = {zero[i], one[i]};
        p[i].push_back(i);
        if(i >= 1) pq.push({fv[i], i});
    }
    while(pq.size()){
        auto [f, idx] = pq.top();
        pq.erase(pq.top());
        int r = uf.root(idx);
        if(G[r] == -1) continue;
        int prv = uf.root(G[r]);
        int nxt = uf.unite(r, prv);
        G[nxt] = G[prv];
        inv[nxt] += fv[prv].q * fv[r].p;
        {
            if(p[r].size() < p[prv].size()){
                while(!p[r].empty()){
                    int x = p[r].front();
                    p[r].pop_front();
                    p[prv].push_back(x);
                }
                if(prv != nxt) std::swap(p[prv], p[nxt]);
            }else{
                while(!p[prv].empty()){
                    int x = p[prv].back();
                    p[prv].pop_back();
                    p[r].push_front(x);
                }
                if(r != nxt) std::swap(p[r], p[nxt]);
            }
        }
        std::pair<fraction<T>, int> nf = {fv[prv], prv};
        int from = prv;
        if(nxt == prv) from = r;
        inv[nxt] += inv[from];
        fv[nxt].p += fv[from].p;
        fv[nxt].q += fv[from].q;
        if(G[nxt] != -1){
            pq.erase(nf);
            pq.push({fv[nxt], nxt});
        }
    }
    std::vector<int> res;
    while(!p[uf.root(0)].empty()){
        int x = p[uf.root(0)].front();
        p[uf.root(0)].pop_front();
        res.push_back(x);
    }
    return {inv[uf.root(0)], res};
}

#line 2 "lib/graph/rooted_tree_topological_order_with_minimum_inversions.hpp"

#include <iostream>
#include <vector>
#include <queue>
#line 2 "lib/data_structure/union_find.hpp"

/**
 * @brief Union-Find
 * @docs docs/data_structure/union_find.md
 */

#line 9 "lib/data_structure/union_find.hpp"
#include <cassert>

struct UnionFind{
    int V;
    std::vector<int> par;
    std::vector<int> edg;

    UnionFind(const int N) : V(N), par(N), edg(N){
        for(int i = 0; i < N; ++i){
            par[i] = -1;
            edg[i] = 0;
        }
    }

    int root(int x){
        assert(0 <= x && x < V);
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    int unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx == ry){
            edg[rx]++;
            return rx;
        }
        if(-par[rx] < -par[ry]) std::swap(rx, ry);
        par[rx] = par[rx] + par[ry];
        par[ry] = rx;
        edg[rx] += edg[ry] + 1;
        return rx;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    long long size(int x){
        return -par[root(x)];
    }

    long long edge(int x){
        return edg[root(x)];
    }
};
#line 2 "lib/data_structure/priority_queue.hpp"

/**
 * @brief Eraseable Priority Queue (削除可能優先度付きキュー)
 */

#line 9 "lib/data_structure/priority_queue.hpp"

template <typename T>
struct PriorityQueue{
    std::priority_queue<T> q, removed_q;

    PriorityQueue(){ }

    void normalize(){
        while(!q.empty() && !removed_q.empty()){
            if(q.top() == removed_q.top()){
                q.pop();
                removed_q.pop();
            } else{
                break;
            }
        }
    }

    void push(const T &x){
        q.push(x);
    }

    void erase(const T &x){
        removed_q.push(x);
    }

    size_t size(){
        return q.size() - removed_q.size();
    }

    bool empty(){
        return (size() == 0);
    }

    T top(){
        normalize();
        assert(!q.empty());
        return q.top();
    }
};
#line 8 "lib/graph/rooted_tree_topological_order_with_minimum_inversions.hpp"

template <typename T>
struct fraction{
    T p, q; // long long or BigInt
    fraction(T P = 0, T Q = 1) : p(P), q(Q){}
    inline bool operator==(const fraction &other) const {
        return p * other.q == other.p * q;
    }
    inline bool operator<(const fraction &other) const {
        if(other.p == 0 && other.q == 0) return false;
        if(p == 0 && q == 0) return true;
        return p * other.q < other.p * q;
    }
};

template <typename T>
std::pair<T, std::vector<int>> rootedTreeTopologicalOrderWithMinimumInversions(const std::vector<int> &par, const std::vector<T> &zero, const std::vector<T> &one){
    std::vector<int> G = par;
    int n = G.size();
    UnionFind uf(n);
    PriorityQueue<std::pair<fraction<T>, int>> pq;
    std::vector<T> inv(n);
    std::vector<fraction<T>> fv(n);
    std::vector<std::deque<int>> p(n);
    for(int i = 0; i < n; ++i){
        fv[i] = {zero[i], one[i]};
        p[i].push_back(i);
        if(i >= 1) pq.push({fv[i], i});
    }
    while(pq.size()){
        auto [f, idx] = pq.top();
        pq.erase(pq.top());
        int r = uf.root(idx);
        if(G[r] == -1) continue;
        int prv = uf.root(G[r]);
        int nxt = uf.unite(r, prv);
        G[nxt] = G[prv];
        inv[nxt] += fv[prv].q * fv[r].p;
        {
            if(p[r].size() < p[prv].size()){
                while(!p[r].empty()){
                    int x = p[r].front();
                    p[r].pop_front();
                    p[prv].push_back(x);
                }
                if(prv != nxt) std::swap(p[prv], p[nxt]);
            }else{
                while(!p[prv].empty()){
                    int x = p[prv].back();
                    p[prv].pop_back();
                    p[r].push_front(x);
                }
                if(r != nxt) std::swap(p[r], p[nxt]);
            }
        }
        std::pair<fraction<T>, int> nf = {fv[prv], prv};
        int from = prv;
        if(nxt == prv) from = r;
        inv[nxt] += inv[from];
        fv[nxt].p += fv[from].p;
        fv[nxt].q += fv[from].q;
        if(G[nxt] != -1){
            pq.erase(nf);
            pq.push({fv[nxt], nxt});
        }
    }
    std::vector<int> res;
    while(!p[uf.root(0)].empty()){
        int x = p[uf.root(0)].front();
        p[uf.root(0)].pop_front();
        res.push_back(x);
    }
    return {inv[uf.root(0)], res};
}

Back to top page