Submit Info #29442

Problem Lang User Status Time Memory
Dominator Tree cpp FlowerOfSorrow AC 70 ms 24.40 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.37 MiB
example_01 AC 1 ms 0.67 MiB
random_00 AC 20 ms 14.48 MiB
random_01 AC 70 ms 24.40 MiB
random_02 AC 14 ms 7.67 MiB
random_03 AC 31 ms 18.73 MiB
random_04 AC 2 ms 2.11 MiB

#include <bits/stdc++.h> using namespace std; template<class T> struct graph{ struct edge{ int from, to; T cost; }; int n; vector<edge> edges; vector<vector<int>> adj; function<bool(int)> ignore; // edge ignoration rule graph(int n): n(n), adj(n), ignore(nullptr){ } int link(int u, int v, T w = 1){ // insert an undirected edge int id = (int)edges.size(); adj[u].push_back(id), adj[v].push_back(id), edges.push_back({u, v, w}); return id; } int orient(int u, int v, T w = 1){ // insert a directed edge int id = (int)edges.size(); adj[u].push_back(id), edges.push_back({u, v, w}); return id; } graph reversed() const{ // returns the transpose of the directed graph graph res(n); for(auto &e: edges) res.orient(e.to, e.from, e.cost); res.ignore = ignore; return res; } }; // Requries graph template<class T> vector<int> find_dominators(graph<T> &g, int root){ int n = g.n; vector<int> pos(n, -1), order, parent(n, -1); function<void(int)> dfs = [&](int u){ pos[u] = (int)order.size(); order.push_back(u); for(auto id : g.adj[u]){ if(g.ignore != nullptr && g.ignore(id)) continue; auto &e = g.edges[id]; int v = e.to; if(!~pos[v]){ parent[v] = u; dfs(v); } } }; dfs(root); vector<int> p(n), best(n), sdom = pos; iota(p.begin(), p.end(), 0), iota(best.begin(), best.end(), 0); function<int(int)> find_best = [&](int x){ if(p[x] != x){ int u = find_best(p[x]); if(sdom[u] < sdom[best[x]]) best[x] = u; p[x] = p[p[x]]; } if(sdom[best[p[x]]] < sdom[best[x]]) best[x] = best[p[x]]; return best[x]; }; graph<int> g_rev = g.reversed(); vector<int> idom(n, -1), link(n, -1); vector<vector<int>> bucket(n); for(int it = (int)order.size() - 1; it >= 0; -- it){ int w = order[it]; for(auto id : g_rev.adj[w]){ if(g_rev.ignore != nullptr && g_rev.ignore(id)) continue; auto &e = g_rev.edges[id]; int u = e.to; if(~pos[u]) sdom[w] = min(sdom[w], sdom[find_best(u)]); } idom[w] = order[sdom[w]]; for(auto u: bucket[w]) link[u] = find_best(u); for(auto id: g.adj[w]){ if(g.ignore != nullptr && g.ignore(id)) continue; auto &e = g.edges[id]; int u = e.to; if(parent[u] == w) p[u] = w; } bucket[order[sdom[w]]].push_back(w); } for(int it = 1; it < (int)order.size(); ++ it) idom[order[it]] = idom[link[order[it]]]; return idom; // idom[i] -- immediate dominator for vertex i } int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int n, m, s; cin >> n >> m >> s; graph<int> g(n); for(auto i = 0; i < m; ++ i){ int u, v; cin >> u >> v; g.orient(u, v); } for(auto p: find_dominators(g, s)){ cout << p << " "; } cout << "\n"; return 0; } /* */ //////////////////////////////////////////////////////////////////////////////////////// // // // Coded by Aeren // // // ////////////////////////////////////////////////////////////////////////////////////////