graph/DominatorTree.cpp

• View this file on GitHub
• Last update: 2024-09-09 12:29:49+00:00

Code

/**
 * Author: Alexey Vasilyev
 * Date: ?
 * Description: Dominator tree
 * Time: ?
 */

struct DominatorTree {
    vector<basic_string<int>> g, rg, bucket;
    basic_string<int> arr, par, rev, sdom, dom, dsu, label;
    int n, t;

    DominatorTree(int n) : g(n), rg(n), bucket(n), arr(n, -1), par(n, -1), rev(n, -1), 
    sdom(n, -1), dom(n, -1), dsu(n, 0), label(n, 0), n(n), t(0) {}
    void add_edge(int u, int v) {
        g[u] += v;
    }
    void dfs(int u) {
        arr[u] = t;
        rev[t] = u;
        label[t] = sdom[t] = dsu[t] = t;
        t++;
        for (int w : g[u]) {
            if (arr[w] == -1) {
                dfs(w);
                par[arr[w]] = arr[u];
            }
            rg[arr[w]] += arr[u];
        }
    }
    int find(int u, int x=0) {
        if (u == dsu[u]) return x ? -1 : u;
        int v = find(dsu[u], x + 1);
        if (v < 0) return u;
        if (sdom[label[dsu[u]]] < sdom[label[u]])
            label[u] = label[dsu[u]];
        dsu[u] = v;
        return x ? v : label[u];
    }
    vector<int> run(int root) {
        dfs(root);
        iota(dom.begin(), dom.end(), 0);
        for (int i = t - 1; i >= 0; --i) {
            for (int w : rg[i]) sdom[i] = min(sdom[i], sdom[find(w)]);
            if (i) bucket[sdom[i]] += i;
            for (int w : bucket[i]) {
                int v = find(w);
                if (sdom[v] == sdom[w]) dom[w] = sdom[w];
                else dom[w] = v;
            }
            if (i > 1) dsu[i] = par[i];
        }
        for (int i = 1; i < t; i++) if (dom[i] != sdom[i]) dom[i] = dom[dom[i]];
        vector<int> outside_dom(n, -1);
        for (int i = 1; i < t; i++) outside_dom[rev[i]] = rev[dom[i]];
        //-1 if vertex is not reachable
        return outside_dom;
    }
};

#line 1 "graph/DominatorTree.cpp"
/**
 * Author: Alexey Vasilyev
 * Date: ?
 * Description: Dominator tree
 * Time: ?
 */

struct DominatorTree {
    vector<basic_string<int>> g, rg, bucket;
    basic_string<int> arr, par, rev, sdom, dom, dsu, label;
    int n, t;

    DominatorTree(int n) : g(n), rg(n), bucket(n), arr(n, -1), par(n, -1), rev(n, -1), 
    sdom(n, -1), dom(n, -1), dsu(n, 0), label(n, 0), n(n), t(0) {}
    void add_edge(int u, int v) {
        g[u] += v;
    }
    void dfs(int u) {
        arr[u] = t;
        rev[t] = u;
        label[t] = sdom[t] = dsu[t] = t;
        t++;
        for (int w : g[u]) {
            if (arr[w] == -1) {
                dfs(w);
                par[arr[w]] = arr[u];
            }
            rg[arr[w]] += arr[u];
        }
    }
    int find(int u, int x=0) {
        if (u == dsu[u]) return x ? -1 : u;
        int v = find(dsu[u], x + 1);
        if (v < 0) return u;
        if (sdom[label[dsu[u]]] < sdom[label[u]])
            label[u] = label[dsu[u]];
        dsu[u] = v;
        return x ? v : label[u];
    }
    vector<int> run(int root) {
        dfs(root);
        iota(dom.begin(), dom.end(), 0);
        for (int i = t - 1; i >= 0; --i) {
            for (int w : rg[i]) sdom[i] = min(sdom[i], sdom[find(w)]);
            if (i) bucket[sdom[i]] += i;
            for (int w : bucket[i]) {
                int v = find(w);
                if (sdom[v] == sdom[w]) dom[w] = sdom[w];
                else dom[w] = v;
            }
            if (i > 1) dsu[i] = par[i];
        }
        for (int i = 1; i < t; i++) if (dom[i] != sdom[i]) dom[i] = dom[dom[i]];
        vector<int> outside_dom(n, -1);
        for (int i = 1; i < t; i++) outside_dom[rev[i]] = rev[dom[i]];
        //-1 if vertex is not reachable
        return outside_dom;
    }
};

Back to top page