Submit Info #43213

Problem Lang User Status Time Memory
Dominator Tree cpp Lain AC 51 ms 19.05 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
example_01 AC 1 ms 0.64 MiB
random_00 AC 17 ms 14.29 MiB
random_01 AC 51 ms 19.05 MiB
random_02 AC 13 ms 6.80 MiB
random_03 AC 24 ms 18.52 MiB
random_04 AC 2 ms 2.21 MiB

#include "bits/stdc++.h" using namespace std; using ll = long long; using pii = pair<int,int>; // Dominator Tree, a directed tree with root S with edges from the immediate // dominator to the vertex. // Dominator = necessary vertex to get from S to v // Uses 1-indexed values // TODO: switch to 0 indexed struct DominatorTree { int n; // Size of arrays, number of vertices + 1 int timer; // DFS timer vector<vector<int>> adj; // Adjacency list vector<vector<int>> radj; // Reverse adjacency list on labels vector<vector<int>> rdom; vector<int> s, rs; // new labels depending on timer and inverse vector<int> par, val; vector<int> sdom; // Label of semi dominator vector<int> dom; // Label of immediate dominator vector<int> rp; vector<int> up; // Points to the immediate dominator. If up[i] = S, no required vertex // _n is the number of vertices, n is the size of the arrays. DominatorTree(int _n):n(_n+1),timer(0),adj(n), radj(n), rdom(n), s(n), rs(n), par(n), val(n), sdom(n), dom(n), rp(n), up(n) {} void add_edge(int u, int v) { adj[u].push_back(v); } void unite(int u, int v) { par[u] = v; } int find(int x, int c = 0) { if (par[x] == x) return c? -1 : x; int p = find(par[x],1); if (p == -1) return c ? par[x] : val[x]; if (sdom[val[x]] > sdom[val[par[x]]]) val[x] = val[par[x]]; par[x] = p; return c ? p : val[x]; } void dfs(int x) { rs[s[x] = ++timer] = x; par[timer] = sdom[timer] = val[timer] = timer; for (int v : adj[x]) { if (s[v] == 0) dfs(v), rp[s[v]] = s[x]; radj[s[v]].push_back(s[x]); } } int build(int s) { dfs(s); for (int i = timer; i ; i--) { for (int u : radj[i]) sdom[i] = min(sdom[i], sdom[find(u)]); if (i > 1) rdom[sdom[i]].push_back(i); for (int u : rdom[i]) { int p = find(u); if (sdom[p] == i) dom[u] = i; else dom[u] = p; } if (i > 1) unite(i,rp[i]); } for (int i = 2; i <= timer; i++) if (sdom[i] != dom[i]) dom[i] = dom[dom[i]]; for (int i = 2; i <= timer; i++) up[rs[i]] = rs[dom[i]]; return timer; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m,s; cin >> n >> m >> s; s++; DominatorTree d(n); for (int i =0; i < m; i++) { int u,v; cin >> u >> v; u++,v++; d.add_edge(u,v); } d.build(s); for (int i = 1; i <= n; i++){ if (i == s) { cout << s-1 << " "; } else cout << d.up[i]-1 << " "; } cout << '\n'; }