Submit Info #45786

Problem Lang User Status Time Memory
Dominator Tree cpp KNKMT AC 112 ms 20.33 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
example_01 AC 1 ms 0.61 MiB
random_00 AC 28 ms 13.36 MiB
random_01 AC 112 ms 20.33 MiB
random_02 AC 21 ms 6.80 MiB
random_03 AC 40 ms 17.43 MiB
random_04 AC 0 ms 2.08 MiB

#include <iostream> #include <vector> #include<iomanip> #include<functional> #include<algorithm> #include<deque> #include<math.h> #include<set> #include<cstdio> #include<string> #include<queue> #include<complex> #include<numeric> #include<stack> #include<unordered_map> #include<map> #include <cassert> using namespace std; #define rep(i,n) for(int i = 0;i<n;i++) #define req(i,n) for(ll i = 1;i<=n;i++) #define rrep(i,n) for(int i = n-1;i>=0;i--) #define ALL(a) a.begin(),a.end() template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } typedef long long ll; typedef long double ld; const ll mod = 1e9 + 7; struct DominatorTree {// 根 s からある頂点 tから通る時の必ず通る点のうち最もsに近い点 struct UnionFind { vector<int>& semi; vector<int>ps, ms; UnionFind(vector<int>& semi) :semi(semi), ps(semi.size()), ms(semi.size()) { iota(ALL(ps), 0); iota(ALL(ms), 0); }int find(int v) { if (ps[v] == v)return v; int r = find(ps[v]); if (semi[ms[v]] > semi[ms[ps[v]]]) ms[v] = ms[ps[v]]; return ps[v] = r; }int eval(int v) { find(v); return ms[v]; }void link(int p, int v) { ps[v] = p; } }; vector<vector<int>> G, R; vector<int> ord, par, idom, semi; DominatorTree(int n): G(n), R(n), par(n), idom(n, -1), semi(n, -1) { ord.reserve(n); }void add_edge(int u, int v) { G[u].push_back(v); R[v].push_back(u); }void dfs(int v) { semi[v] = ord.size(); ord.push_back(v); for (int u : G[v]) { if (~semi[u])continue; par[u] = v; dfs(u); } }void build(int rt) { dfs(rt); int n = G.size(); vector<vector<int>> bkt(n); UnionFind uf(semi); vector<int> us(n); rrep(i, ord.size()) { int v = ord[i]; for (int u : R[v]) { if (semi[u] < 0)continue; u = uf.eval(u); if (semi[v] > semi[u])semi[v] = semi[u]; }bkt[ord[semi[v]]].push_back(v); for (int u : bkt[par[v]]) us[u] = uf.eval(u); bkt[par[v]].clear(); uf.link(par[v], v); }req(i, ord.size()-1) { int v = ord[i], u = us[v]; idom[v] = (semi[v] == semi[u] ? semi[v] : idom[u]); }req(i, ord.size() - 1) { int v = ord[i]; idom[v] = ord[idom[v]]; }idom[rt] = rt; }int operator[](int k) { return idom[k]; } }; int main() { int n, m, s; cin >> n >> m >> s; DominatorTree G(n); rep(i, m) { int a, b; cin >> a >> b; G.add_edge(a, b); }G.build(s); rep(i, n) { if (i != 0)cout << " "; cout << G[i]; }cout << endl; }