支配树

        点支配问题是图上的一类问题，可以用支配树这一利器解决。

支配点与支配树

        在一个有向图中，如果从x到y的所有路径都会经过一个点r，则称r支配y。对于y的所有支配点，离y最近的一个称为（最近）支配点，记作idom[y]。所有的点引一条边连向idom，可以得到一棵树，称为支配树。支配树的根结点为x，并且从x到y路径上的所有点都支配y，这体现了支配的传递性。

DAG上的支配树

        如何求支配树是一个具有实际意义的问题，下面先从简单情况谈起：对于DAG上的支配树求法。来看一道模板题。
        显然，一个生物的灾难值就是其支配的点的数目，体现在支配树上就是其子树上结点数目减去一。由于可能有多个生产者，我们需要引入一个超级源点作为根，再构造支配树。下面就考虑如何在DAG上构造支配树。
        第一步，对给定的图进行拓扑排序，得到一个拓扑序列。
        第二步，按照拓扑序从小到大开始，依次将每一个点放到支配树上。假定现在需要将x这个结点放入支配树中，并且其之前的所有点均已加入支配树。然后求出该结点所有前驱的支配点，该支配点就是x的支配点。这是因为必须经过该结点的某一个前驱才能到达该结点，否则不可达，因此所有前驱共同的支配点就是x的支配点。那如何求前驱的支配点？不要忘了前驱的拓扑序小于x，它们必然已经加入了支配树，因此它们的LCA就是共同的支配点。这里用一步在线求LCA的倍增算法即可完成。时间复杂度为线性对数阶。

#include<bits/stdc++.h>

#define N  (65534+50)
using namespace std;
vector<int> ch[N], ch_opp[N], tree[N];
int n, st[N], depth[N], grand[N][20], ans[N], in[N];
int t = 0;

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

inline void topSort() {//拓扑排序
    queue<int> que;
    for (int i = 1; i <= n; i++)
        if (!in[i])ch[0].push_back(i), ch_opp[i].push_back(0), que.push(i);//0是超级源点
    while (!que.empty()) {
        int f = que.front();
        que.pop(), st[++t] = f;//排序结果放到s中
        for (int i = 0; i < ch[f].size(); i++) {
            --in[ch[f][i]];
            if (!in[ch[f][i]]) que.push(ch[f][i]);
        }
    }
}

inline int lca(int x, int y) {//倍增法求LCA
    if (depth[x] > depth[y])swap(x, y);//y的深度大
    if (depth[x] != depth[y]) {
        for (int i = 17; i >= 0; i--)if (depth[grand[y][i]] >= depth[x])y = grand[y][i];
    }
    if (x == y)return x;
    for (int i = 17; i >= 0; i--) {
        if (grand[x][i] != grand[y][i])x = grand[x][i], y = grand[y][i];
    }
    return grand[x][0];
}

int DFS(int x) {
    if (tree[x].empty())return ans[x] = 1;
    for (int i = 0; i < tree[x].size(); i++)ans[x] += DFS(tree[x][i]);
    return ++ans[x];
}

int main() {
    n = read(), depth[0] = 1;
    for (int i = 1; i <= n; i++) {
        int x = read();
        while (x)ch[x].push_back(i), ch_opp[i].push_back(x), ++in[i], x = read();//建图
    }
    topSort();
    for (int i = 1; i <= n; i++) {
        int f = ch_opp[st[i]][0];//第一个前驱
        for (int j = 1; j < ch_opp[st[i]].size(); j++)f = lca(f, ch_opp[st[i]][j]);//求共同的LCA
        tree[f].push_back(st[i]), grand[st[i]][0] = f, depth[st[i]] = depth[f] + 1;//更新
        for (int j = 1; j <= 17; j++)grand[st[i]][j] = grand[grand[st[i]][j - 1]][j - 1];
    }
    DFS(0);//一遍DFS求子树结点数目
    for (int i = 1; i <= n; i++)printf("%d\n", ans[i] - 1);//减去一就是答案
    return 0;
}

Lengauer−Tarjan算法

        DAG上的求支配树方法比较容易，但是对于可以有环的有向图，支配树便不是那么易求。这里介绍在线性对数时间复杂度下求解有向图支配树的Lengauer-Tarjan算法。

半必经点

        首先，我们需要DFS树，对有向图中点进行DFN排序。
        对于x到y，如果存在一条路径使得这条路径上的所有点（除了x和y本身）的DFN都大于DFN[x]，则称x为y的半必经点。这其中DFN值最小的一个称为最小半必经点（半支配点），即为sdom[y]=x。特别地，y的所有前驱结点都是y的半必经点。
        可以证明，在DFS树上，添加sdom[x]到x的有向边后，得到的DAG的支配关系与原图一致，这样可以将有环的有向图转化为DAG，但是这不是很优秀的做法。
        按照DFN从大到小枚举每一个点，对于一个点x，先枚举其前驱，如果其DFN小，则比较其与sdom[x]，取更小的一个。如果前驱DFN大于DFN[x]，则该前驱一定不会成为sdom[x]，这时取前驱在已经构造的树（是指目前已经经过遍历的点及其邻边在DFS树上的部分）上的满足DFN[z]>DFN[x]的祖先z，对比sdom[x]和sdom[z]的DFN来更新x的sdom。这里的操作可以用加权并查集实现，权值定义为到根DFN[sdom[x]]最小的x。
        下一步就是半必经点转支配点。
        找到sdom[x]到x路径上（不含sdom[x]）使得DFN[sdom[z]]最小的z点，此时如果sdom[z]=sdom[x]，则idom[x]=sdom[x]，否则idom[x]就是idom[z]。模板题。

#include<bits/stdc++.h>

#define N 200005
#define M 300005
using namespace std;
struct Edge {
    int to, next;
} edge[M * 5];
int head[N], pre[N], cat[N], tree[N], n, m, father[N], DFN[N], DFNCNT, cnt = 1;
int sdom[N], idom[N], val[N], fa[N], rk[N], ans[N];

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

inline void add(int *p, int x, int y) {
    edge[cnt].to = y, edge[cnt].next = p[x], p[x] = cnt++;
}

void DFS(int x) {
    DFN[x] = ++DFNCNT, rk[DFNCNT] = x;//建立DFN到点的映射
    for (int i = head[x]; i; i = edge[i].next) {
        if (!DFN[edge[i].to])DFS(edge[i].to), fa[edge[i].to] = x;//记录fa
    }
}

int find(int x) {
    if (father[x] == x)return x;
    int rt = find(father[x]);
    if (DFN[sdom[val[father[x]]]] < DFN[sdom[val[x]]])val[x] = val[father[x]];
    return father[x] = rt;
}

inline void tarjan() {//板子...
    for (int i = DFNCNT; i >= 2; i--) {//反向遍历
        int now = rk[i], res = n;
        for (int j = pre[now]; j; j = edge[j].next) {//处理前驱
            if (!DFN[edge[j].to])continue;
            if (DFN[edge[j].to] < DFN[now])res = min(res, DFN[edge[j].to]);//更新答案
            else find(edge[j].to), res = min(res, DFN[sdom[val[edge[j].to]]]);
        }
        sdom[now] = rk[res], father[now] = fa[now], add(cat, sdom[now], now), now = fa[now];//并查集合并，图的建立
        for (int j = cat[now]; j; j = edge[j].next) {//更新一波idom
            find(edge[j].to);
            if (sdom[val[edge[j].to]] == now)idom[edge[j].to] = now;//就是idom[edge[j].to] = sdom[val[edge[j].to]]
            else idom[edge[j].to] = val[edge[j].to];
        }
    }
    for (int i = 2, now; i <= DFNCNT; i++) {
        now = rk[i];
        if (idom[now] != sdom[now])idom[now] = idom[idom[now]];
    }
}

int DFS_ans(int x) {
    if (!tree[x])return ans[x] = 1;
    for (int i = tree[x]; i; i = edge[i].next)ans[x] += DFS_ans(edge[i].to);
    return ++ans[x];
}

int main() {
    n = read(), m = read();
    for (int i = 0; i < m; i++) {
        int x = read(), y = read();
        add(head, x, y), add(pre, y, x);//建立反图
    }
    for (int i = 1; i <= n; i++)val[i] = sdom[i] = father[i] = i;//初始化
    DFS(1), tarjan(), cnt = 1;
    for (int i = 2; i <= n; i++)if (idom[i])add(tree, idom[i], i);//建立支配树
    DFS_ans(1);
    for (int i = 1; i <= n; i++)cout << ans[i] << " ";
    return 0;
}