Dominator Tree for DAG

adj[u] contains child of u in dominator tree
par[u] contains parent of u in DAG
dom[u] = immediate dominator of u

vector <int> adj[maxn], par[maxn], topo;
int dom[maxn], depth[maxn], father[maxn][logn], vis[maxn];

void addEdge(int u, int v) // Construct DAG using this function
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void dfs(int u) // topological sort
{
    if (vis[u])
        return;
    vis[u] = 1;
    for (int v : adj[u])
    {
        if (vis[v])
            continue;
        dfs(v);
    }
    topo.push_back(u);
}

void addToTree(int par, int u) // Adds edge (par, u) to dominator tree
{
    dom[u] = par;
    father[u][0] = par;
    depth[u] = depth[par] + 1;
    for (int i = 1; i < logn-1; i++)
    {
        if (father[u][i-1] + 1)
        {
             father[u][i] = father[ father[u][i-1] ][i-1];
        }
    }
}

int lca(int u, int v)
{
    if (depth[u] < depth[v])
        swap(u, v);
    for (int i = logn-1; i >= 0; i--)
    {
        if (father[u][i] + 1 && depth[ father[u][i] ] >= depth[v])
        {
            u = father[u][i];
        }
    }
    if (u == v)
        return u;
    for (int i = logn-1; i >= 0; i--)
    {
        if (father[u][i] � father[v][i])
        {
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}

void dominatorTree(int root)
{
    dfs(root);
    memo(father, -1);
    memo(dom, -1);


    for (int i = (int)topo.size()�2; i >= 0; i--)
    {
        int u = topo[i];
        int d = -1;
        for (int v : par[u])
            d = d == -1 ? v : lca(v, d);
        addToTree(d, u);
    }
}
adj[u] contains child of u in dominator tree
par[u] contains parent of u in DAG
dom[u] = immediate dominator of u

vector <int> adj[maxn], par[maxn], topo;
int dom[maxn], depth[maxn], father[maxn][logn], vis[maxn];

void addEdge(int u, int v) // Construct DAG using this function
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void dfs(int u) // topological sort
{
    if (vis[u])
        return;
    vis[u] = 1;
    for (int v : adj[u])
    {
        if (vis[v])
            continue;
        dfs(v);
    }
    topo.push_back(u);
}

void addToTree(int par, int u) // Adds edge (par, u) to dominator tree
{
    dom[u] = par;
    father[u][0] = par;
    depth[u] = depth[par] + 1;
    for (int i = 1; i < logn-1; i++)
    {
        if (father[u][i-1] + 1)
        {
             father[u][i] = father[ father[u][i-1] ][i-1];
        }
    }
}

int lca(int u, int v)
{
    if (depth[u] < depth[v])
        swap(u, v);
    for (int i = logn - 1; i >= 0; i--)
    {
        if (father[u][i] + 1 && depth[ father[u][i] ] >= depth[v])
        {
            u = father[u][i];
        }
    }
    if (u == v)
        return u;
    for (int i = logn-1; i >= 0; i--)
    {
        if (father[u][i] != father[v][i])
        {
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}

void dominatorTree(int root)
{
    dfs(root);
    memo(father, -1);
    memo(dom, -1);


    for (int i = (int)topo.size() - 2; i >= 0; i--)
    {
        int u = topo[i];
        int d = -1;
        for (int v : par[u])
            d = d == -1 ? v : lca(v, d);
        addToTree(d, u);
    }
}               adj[u] contains child of u in dominator tree
par[u] contains parent of u in DAG
dom[u] = immediate dominator of u

vector <int> adj[maxn], par[maxn], topo;
int dom[maxn], depth[maxn], father[maxn][logn], vis[maxn];

void addEdge(int u, int v) // Construct DAG using this function
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void dfs(int u) // topological sort
{
    if (vis[u])
        return;
    vis[u] = 1;
    for (int v : adj[u])
    {
        if (vis[v])
            continue;
        dfs(v);
    }
    topo.push_back(u);
}

void addToTree(int par, int u) // Adds edge (par, u) to dominator tree
{
    dom[u] = par;
    father[u][0] = par;
    depth[u] = depth[par] + 1;
    for (int i = 1; i < logn-1; i++)
    {
        if (father[u][i-1] + 1)
        {
             father[u][i] = father[ father[u][i-1] ][i-1];
        }
    }
}

int lca(int u, int v)
{
    if (depth[u] < depth[v])
        swap(u, v);
    for (int i = logn-1; i >= 0; i--)
    {
        if (father[u][i] + 1 && depth[ father[u][i] ] >= depth[v])
        {
            u = father[u][i];
        }
    }
    if (u == v)
        return u;
    for (int i = logn-1; i >= 0; i--)
    {
        if (father[u][i] � father[v][i])
        {
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}

void dominatorTree(int root)
{
    dfs(root);
    memo(father, -1);
    memo(dom, -1);


    for (int i = (int)topo.size()�2; i >= 0; i--)
    {
        int u = topo[i];
        int d = -1;
        for (int v : par[u])
            d = d == -1 ? v : lca(v, d);
        addToTree(d, u);
    }
}
adj[u] contains child of u in dominator tree
par[u] contains parent of u in DAG
dom[u] = immediate dominator of u

vector <int> adj[maxn], par[maxn], topo;
int dom[maxn], depth[maxn], father[maxn][logn], vis[maxn];

void addEdge(int u, int v) // Construct DAG using this function
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void dfs(int u) // topological sort
{
    if (vis[u])
        return;
    vis[u] = 1;
    for (int v : adj[u])
    {
        if (vis[v])
            continue;
        dfs(v);
    }
    topo.push_back(u);
}

void addToTree(int par, int u) // Adds edge (par, u) to dominator tree
{
    dom[u] = par;
    father[u][0] = par;
    depth[u] = depth[par] + 1;
    for (int i = 1; i < logn-1; i++)
    {
        if (father[u][i-1] + 1)
        {
             father[u][i] = father[ father[u][i-1] ][i-1];
        }
    }
}

int lca(int u, int v)
{
    if (depth[u] < depth[v])
        swap(u, v);
    for (int i = logn - 1; i >= 0; i--)
    {
        if (father[u][i] + 1 && depth[ father[u][i] ] >= depth[v])
        {
            u = father[u][i];
        }
    }
    if (u == v)
        return u;
    for (int i = logn-1; i >= 0; i--)
    {
        if (father[u][i] != father[v][i])
        {
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}

void dominatorTree(int root)
{
    dfs(root);
    memo(father, -1);
    memo(dom, -1);


    for (int i = (int)topo.size() - 2; i >= 0; i--)
    {
        int u = topo[i];
        int d = -1;
        for (int v : par[u])
            d = d == -1 ? v : lca(v, d);
        addToTree(d, u);
    }
}