Pre

看了两天，终于看懂了(比\(\frac{1}{\infty}\)高阶的无穷小)\(\%\)。

Hints

1、初始化的三个数组要记住\(val.f.sdom\)。

2、\(find\)函数有一点神奇，之前没有见过，可以熟悉一下。

3、\(69\)~\(71\)行的代码，就是更新\(sdom\)的那一部分，考虑转移到\(sdom(x)\)。

当\(dfn(y)<dfn(x)\)

\(y\)还没有被访问并更新答案，因为我们是按照从大到小的顺序操作的，所以\(sdom(x)=y\)。

当\(dfn(y)>dfn(x)\)

\(y\)已经被更新，但是\(y\)的第二浅的老祖宗的\(dfn\)不会小于\(x\)，最浅的老祖宗可以作为\(sdom(x)\)因为满足之间的点的\(dfn\)大于\(dfn(x)\)，所以可以转移。

4、注意\(73\)行转移到\(tree\)的图里面。

5、\(83\)行，这是一个神奇的东西。因为\(idom(st.val(v))\)在这个时候时可能没有初始化的，为\(0\)，又不能够在程序开始初始化，所以只有最后处理完了再来处理这个地方。

(开始的时候我以为我少考虑了几种情况，结果浪费了\(1\)个小时找推理错误，发现没有错)。

6、注意在\(tarjan\)函数的里面一定要执行\(find\)函数，我已经\(WA\)了两次了。

7、最重要的，大致思路要知道。

下面的代码是洛谷的模板题的。

Code

#include 
    
     #define ll long long#define ull unsigned long long#define xx first#define yy second using namespace std;const int N = 200000 + 5, M = 300000 + 5;int n, m, fa[N], sdom[N], idom[N], dfn[N], id[N], cnt, ans[N];struct Graph {    int fr[M << 1], to[M << 1], h[N], tot;    void cal (int u) {        ans[u] = 1;        for (int i = h[u]; i; i = fr[i]) {            cal (to[i]);            ans[u] += ans[to[i]];        }    }    inline void add (int u, int v) {        ++tot;        fr[tot] = h[u];        to[tot] = v;        h[u] = tot;    }    void dfs (int u) {        dfn[u] = ++cnt;        id[cnt] = u;        for (int i = h[u]; i; i = fr[i]) {            if (!dfn[to[i]]) {                dfs (to[i]);                fa[to[i]] = u;            }        }    }}pos, neg, tree, Ans;struct UnionSet {    int f[N], val[N];    inline void init (int n = N - 5) {        for (int i = 1; i <= n; ++i) {            f[i] = i;            val[i] = i;            sdom[i] = i;        }    }    inline void find (int u) {        if (f[u] == u) {            return ;        }        find (f[u]);        int rt = f[f[u]];        if (dfn[sdom[val[f[u]]]] < dfn[sdom[val[u]]]) {            val[u] = val[f[u]];        }        f[u] = rt;    }}st;inline void LT () {    st.init(n);    for (int i = cnt; i >= 2; --i) {        int now = id[i];        for (int j = neg.h[now]; j; j = neg.fr[j]) {            int v = neg.to[j];            st.find (v);            if (dfn[sdom[now]] > dfn[sdom[st.val[v]]]) {                sdom[now] = sdom[st.val[v]];            }        }        tree.add(sdom[now], now);        st.f[now] = fa[now];        now = fa[now];        for (int j =tree.h[now]; j; j = tree.fr[j]) {            int v = tree.to[j];            st.find(v);            if (sdom[st.val[v]] == now) {                idom[v] = now;            }            else {                idom[v] = st.val[v];            }        }    }    for (int i = 1; i <= n; ++i) {        int now = id[i];        if (sdom[now] != idom[now]) {            idom[now] = idom[idom[now]];        }    }}int main () {    scanf ("%d%d", &n, &m);    for (int i = 1; i <= m; ++i) {        int x, y;        scanf ("%d%d", &x, &y);        pos.add (x, y);        neg.add (y, x);    }    pos.dfs (1);    LT ();    for (int i = 1; i <= n; ++i) {        if (idom[i]) {            Ans.add(idom[i], i);        }    }    Ans.cal (1);    for (int i = 1; i <= n; ++i) {        printf ("%d ", ans[i]);    }    return 0;}
    

Concluion

大概就这样。

两天的时间打出了我的支配树代码，接下来想花一些时间做一些相关的题目，熟悉一下。

话说这和Conclusion有什么关系

注意有时候在\(DAG\)上面的时候直接\(LCA\)就可以了。

比如codeforces757F. Team Rocket Rises Again最短路的\(DAG\)上面。