This documentation is automatically generated by competitive-verifier/competitive-verifier
#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> ;
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;
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 |
![]() |
5 ms | 4 MB |
g++ | example_01 |
![]() |
4 ms | 4 MB |
g++ | gen_tree_00 |
![]() |
92 ms | 32 MB |
g++ | gen_tree_01 |
![]() |
91 ms | 32 MB |
g++ | gen_tree_02 |
![]() |
89 ms | 32 MB |
g++ | gen_tree_2_00 |
![]() |
105 ms | 33 MB |
g++ | gen_tree_2_01 |
![]() |
108 ms | 33 MB |
g++ | gen_tree_2_02 |
![]() |
107 ms | 33 MB |
g++ | random_00 |
![]() |
23 ms | 23 MB |
g++ | random_01 |
![]() |
58 ms | 33 MB |
g++ | random_02 |
![]() |
19 ms | 13 MB |
g++ | random_03 |
![]() |
30 ms | 29 MB |
g++ | random_04 |
![]() |
7 ms | 5 MB |
clang++ | example_00 |
![]() |
5 ms | 4 MB |
clang++ | example_01 |
![]() |
4 ms | 4 MB |
clang++ | gen_tree_00 |
![]() |
90 ms | 32 MB |
clang++ | gen_tree_01 |
![]() |
89 ms | 31 MB |
clang++ | gen_tree_02 |
![]() |
91 ms | 32 MB |
clang++ | gen_tree_2_00 |
![]() |
102 ms | 34 MB |
clang++ | gen_tree_2_01 |
![]() |
102 ms | 34 MB |
clang++ | gen_tree_2_02 |
![]() |
102 ms | 34 MB |
clang++ | random_00 |
![]() |
23 ms | 23 MB |
clang++ | random_01 |
![]() |
58 ms | 33 MB |
clang++ | random_02 |
![]() |
18 ms | 13 MB |
clang++ | random_03 |
![]() |
29 ms | 29 MB |
clang++ | random_04 |
![]() |
7 ms | 5 MB |