test/Graph/DominatorTree.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://judge.yosupo.jp/problem/dominatortree

Depends on

• Graph/DominatorTree.cpp
• template.cpp

Code

#include "../../Graph/DominatorTree.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/dominatortree

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, root;
    cin >> n >> m >> root;
    vector<vector<int>> g(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }
    DominatorTree dom(g, root);
    rep(i, n) cout << dom[i] << " ";
    cout << endl;
}

#line 1 "template.cpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template <class T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
using pbds_mset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pbds_trie = trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmin(T &a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
constexpr int INF = 1000000000;
constexpr int64_t llINF = 3000000000000000000;
constexpr double eps = 1e-10;
const double pi = acos(-1);
template <class T>
inline void compress(vector<T> &a) {
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
}
struct linear_sieve {
    vector<int> least_factor, prime_list;
    linear_sieve(int n) : least_factor(n + 1, 0) {
        for (int i = 2; i <= n; i++) {
            if (least_factor[i] == 0) {
                least_factor[i] = i;
                prime_list.push_back(i);
            }
            for (int p : prime_list) {
                if (ll(i) * p > n || p > least_factor[i]) break;
                least_factor[i * p] = p;
            }
        }
    }
};
ll extgcd(ll a, ll b, ll &x, ll &y) {
    // ax+by=gcd(|a|,|b|)
    if (a < 0 || b < 0) {
        ll d = extgcd(abs(a), abs(b), x, y);
        if (a < 0) x = -x;
        if (b < 0) y = -y;
        return d;
    }
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll modpow(ll a, ll b, ll m) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
            res %= m;
        }
        a *= a;
        a %= m;
        b >>= 1;
    }
    return res;
}
template <typename T, typename U>
inline istream &operator>>(istream &is, pair<T, U> &rhs) {
    return is >> rhs.first >> rhs.second;
}
template <typename T>
inline istream &operator>>(istream &is, vector<T> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <typename T, typename U>
inline ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    return os << rhs.first << " " << rhs.second;
}
template <typename T>
inline ostream &operator<<(ostream &os, const vector<T> &v) {
    for (auto itr = v.begin(), end_itr = v.end(); itr != end_itr;) {
        os << *itr;
        if (++itr != end_itr) os << " ";
    }
    return os;
}
#line 2 "Graph/DominatorTree.cpp"
struct DominatorTree {
    vector<vector<int>> g, rg;  // directed
    DominatorTree(vector<vector<int>> g, int root = 0) : g(g) {
        int n = int(g.size());
        par.assign(n, 0);
        idom.assign(n, -1);
        semi.assign(n, -1);
        ord.reserve(n);
        rg.resize(n);
        UnionFind uf(semi);

        dfs(root);
        for (int i = 0; i < n; i++) {
            for (auto &to : g[i]) {
                if (~semi[i]) rg[to].push_back(i);
            }
        }

        vector<vector<int>> bucket(n);
        vector<int> U(n);
        for (int i = (int)ord.size() - 1; i >= 0; i--) {
            int x = ord[i];
            for (int v : rg[x]) {
                v = uf.eval(v);
                if (semi[x] > semi[v]) semi[x] = semi[v];
            }
            bucket[ord[semi[x]]].emplace_back(x);
            for (int v : bucket[par[x]]) U[v] = uf.eval(v);
            bucket[par[x]].clear();
            uf.link(par[x], x);
        }
        for (int i = 1; i < (int)ord.size(); i++) {
            int x = ord[i], u = U[x];
            idom[x] = semi[x] == semi[u] ? semi[x] : idom[u];
        }
        for (int i = 1; i < (int)ord.size(); i++) {
            int x = ord[i];
            idom[x] = ord[idom[x]];
        }
        idom[root] = root;
    }

    int operator[](const int &k) const { return idom[k]; }

    struct UnionFind {
        const vector<int> &semi;
        vector<int> par, m;
        UnionFind(const vector<int> &semi) : semi(semi), par(semi.size()), m(semi.size()) {
            iota(begin(par), end(par), 0);
            iota(begin(m), end(m), 0);
        }

        int find(int v) {
            if (par[v] == v) return v;
            int r = find(par[v]);
            if (semi[m[v]] > semi[m[par[v]]]) m[v] = m[par[v]];
            return par[v] = r;
        }

        int eval(int v) {
            find(v);
            return m[v];
        }

        void link(int p, int c) { par[c] = p; }
    };

    vector<int> ord, par;
    vector<int> idom, semi;

    void dfs(int idx) {
        semi[idx] = (int)ord.size();
        ord.emplace_back(idx);
        for (auto &to : g[idx]) {
            if (~semi[to]) continue;
            dfs(to);
            par[to] = idx;
        }
    }
};
#line 2 "test/Graph/DominatorTree.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/dominatortree

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, root;
    cin >> n >> m >> root;
    vector<vector<int>> g(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }
    DominatorTree dom(g, root);
    rep(i, n) cout << dom[i] << " ";
    cout << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	gen_tree_00	AC	92 ms	32 MB
g++	gen_tree_01	AC	91 ms	32 MB
g++	gen_tree_02	AC	89 ms	32 MB
g++	gen_tree_2_00	AC	105 ms	33 MB
g++	gen_tree_2_01	AC	108 ms	33 MB
g++	gen_tree_2_02	AC	107 ms	33 MB
g++	random_00	AC	23 ms	23 MB
g++	random_01	AC	58 ms	33 MB
g++	random_02	AC	19 ms	13 MB
g++	random_03	AC	30 ms	29 MB
g++	random_04	AC	7 ms	5 MB
clang++	example_00	AC	5 ms	4 MB
clang++	example_01	AC	4 ms	4 MB
clang++	gen_tree_00	AC	90 ms	32 MB
clang++	gen_tree_01	AC	89 ms	31 MB
clang++	gen_tree_02	AC	91 ms	32 MB
clang++	gen_tree_2_00	AC	102 ms	34 MB
clang++	gen_tree_2_01	AC	102 ms	34 MB
clang++	gen_tree_2_02	AC	102 ms	34 MB
clang++	random_00	AC	23 ms	23 MB
clang++	random_01	AC	58 ms	33 MB
clang++	random_02	AC	18 ms	13 MB
clang++	random_03	AC	29 ms	29 MB
clang++	random_04	AC	7 ms	5 MB

Back to top page