tarjan

花了 3-4 天的时间干掉了这个算法：tarjan（虽然只是干掉了板子）

有向图

我刚开始学了一天的无向图，看懂了板子之后，机房大佬告诉我先学有向图的比较好……然后就开始学有向图……
有向图 tarjan 的内容比较少，只有强连通分量，缩点，必经点和必经边

前置定义

给定一个有向图，如果在这个有向图中存在一个点，从它出发可以到达图中所有的点，那么称这个图为：流图
我们在这个流图上进行 dfs，每个点访问一次，所有的访问的点和边构成一棵树，我们称之为搜索树
同时，在 dfs 的过程中，我们搜到每一个点的顺序（1-N），我们把这个点按照这个顺序进行标记，这个标记我们规定它为时间戳，记为 dfn[x]
流图中的每一条有向边(x,y)都必然是以下四种之一： 1.树枝边：搜索树中的边，即：x 是 y 的父节点 2.前向边：x 是 y 的祖先节点但不是父节点 3.后向边：y 是 x 的祖先节点 4.横叉边：（就是除了这三种情况的边）这条边一定满足：$dfn[y] < dfn[x]$;（因为如果 dfn[x] < dfn[y]的话，y 就会成为 x 的子节点）

强连通分量

强联通：存在路径 x->y 也存在路径 y->x 那么 x,y 强联通
给定一张有向图。如果对于图中任意两个节点 x,y 都满足两点强联通，那么这张有向图就是一张强连通图
有向图的极大强连通子图被称为强连通分量，简写为 SCC
那么介绍tarjan 算法：
一个环一定是一张强联通图。tarjan 的基本思路就是对于每一个点 x,都去寻找那些与 x 可以构成环的所有节点将他们放进一个强连通分量中去
容易发现：前向边没用，直接扔掉就好
后向边极其有用，因为有一条后向边就可以形成一个环
横叉边不一定，横叉边过去到另一棵子树上的节点可能是可以回去构成一个环的，也有可能并不能构成环

栈

那么我们为了让这两种边有用途，我们需要维护一个栈保存以下两类节点：

1.搜索树中的祖先节点
如果存在一条后向边，那么构成一个环

2.已经访问过，并且存在一条路径到达祖先节点的点（横叉边）
如果 z 是一个这样的点，从 z 出发存在一条路径到达祖先节点，那么如果存在一条横叉边，就可以构成一个环

（以下几行建议等会再食用）

在实现过程中，对于横叉边，我们进行遍历时，栈中剩下的节点一定是此次访问的节点，并且暂时不属于任何一个强连通分量，那么这个节点一定可以和我们当前的点形成强联通分量（因为这个节点一定可以抵达横叉边对应的边的两个端点的 lca），所以他们一定可以构成一个强连通分量……所以这就是横叉边的用途

进而：我们引入一个概念：追溯值

追溯值

x 的追溯值 low[x]定义为满足以下节点的最小的时间戳：

1.该点在栈中

2.存在一条从 subtree(x)出发的有向边，以该点为终点
根据定义 tarjan 算法按照以下步骤计算追溯值

1. 当节点 x 第一次别访问到的时候，把 x 入栈，初始化 $low[x]=dfn[x]$；

2. 扫描从 x 出发的每一条边（x，y）

   1. 若 y 没有被访问过说明（x，y）是树枝边，递归 y：$low[x]=min(low[x],low[y])$;

   2. 若 y 被访问过并且 y 在栈中，则令 $low[x]=min(low[x],dfn[y])$，但是请注意：在有向图的追溯值中,dfn[y]也可以改为 low[y]（因为只要不一样就算进强连通分量里，详细看第三点），但由于我们的无向图 tarjan 是不能的，所以建议使用 dfn[y]，不容易出锅。另外一条：y 被访问过，并且 y 在栈里，那么说明……这是一条树枝边！（如果不理解，就先记住，看完了下面你会知道为什么我会说这些的）

3. 从 x 回溯之前，判断是否有 low[x]=dfn[x]。若成立，则不断从栈中弹出节点，直至 x 出栈（这点很重要）
   童鞋们可以手摸一下，下面给一组数据：
   1->2 2->3 3->4 4->5 5->2 1->6 6->7 7->4 6->8 8->7 8->9 9->6（编号都直接为 dfn 了，1 为根节点）
   1:1 2:2 3:2 4:2 5:2 6:6 7:7 8:6 9:6 （追溯值）

强连通分量的判定法则：

在追溯值的计算过程中，x 回溯之前 $low[x]=dfn[x]$ 成立，就从栈中从 x 到栈顶所有节点构成一个强连通分量
大致来说，在计算追溯值的第 3 步，如果 $low[x]=dfn[x]$，那么说明 subtree[x]中的所有节点不能与栈里的任何一个其他节点构成环（因为上不去）另外：横叉边的终点时间戳一定比起点时间戳小（上面有说）所以 subtree[x]中的节点不可能到达任何一个没有被访问的节点（子树）（或根节点另一个子树）
又因为我们及时进行了判定和出栈的操作，所以从 x 到栈顶的所有节点构成一个强连通分量，而如果这个强连通分量中的点是某一条没有被搜索到的横叉边的终点，这条横叉边的起点一定不能与这个强连通分量中的点构成强连通分量（就废了），而强连通分量中的点会被 pop 出去，所以 vis 数组会变成 0，所以可以去食用上面的三行了。
程序：

void tarjan(int x)
{
    dfn[x] = low[x] = ++tim;
    sta[++top] = x, vis[x] = 1;
    for (int i = head[x]; i; i = e[i].nex)
        if (!dfn[e[i].v])
        {
            tarjan(e[i].v);
            low[x] = min(low[x], low[e[i].v]);
        }
        else if (vis[e[i].v])
            low[x] = min(low[x], dfn[e[i].v]);
    if (low[x] == dfn[x])
    {
        cnt++;
        int y;
        do
        {
            y = sta[top--], vis[y] = 0;
            c[y] = cnt;
            w[cnt] += a[y];
            sc[cnt]++;
        } while (x != y);
    }
}

由于我们的强连通分量是每一个点都可以互相到达的，那么我们科室适当的考虑一下能不能把这几个点看成一个点来进行问题的处理，这样我们就可以引入一个概念叫做：缩点

我们可以吧每一个 SCC 缩成一个点，对于原图中的每一条有向边，如果 $c[x]!=c[y]$，则在编号为 c[x]和 c[y]的 SCC 之间连上一条边，最后我们会得到一张 DAG(有向无环图)
下面的程序对 SCC 进行缩点操作：以洛谷缩点板子题为例 P3387

void add_c(int x, int y)
{
    ed[++totd] = {y, hd[x]};
    hd[x] = totd;
}
//主函数中
for (int i = 1; i <= n; i++)
{
    for (int j = head[i]; j; j = e[j].nex)
    {
        if (c[i] == c[e[j].v])
            continue;
        in[c[e[j].v]] += 1;//这个是统计入度，因为需要用到拓扑排序
        add_c(c[i], c[e[j].v]);
    }
}

有向图的必经点和必经边

给一张有向图，起点为 S 终点为 T，若从 S 到 T 的每一条路径都经过一个点或者一条边，那它就被称为 S 到 T 的必经点或必经边
Lenguar-tarjan 算法通过计算支配树求出必经点集，但是…………板子题是黑题，我还是不想了
但是还是有方法计算有向无环图的必经点必经边的：

1. 在原图的拓扑序上进行 DP，求出 S 到点 x 的路径条数 fs[x]

2. 在返图上再次 DP 计算从点 x 到终点 T 的路径条数 ft[x]

显然根据乘法原理： 1.对于一条有向边来说（x，y）若 $fs[x]*fs[y]=fs[T]$，则(x,y)是必经边 2.对于一个点 x，若 $fs[x]*ft[x]=fs[T]$ 则 x 是必经点

有向图写完了，就该进行无向图的博客之旅了！（前方道路淤堵。。。请保持好车距。。。）

无向图

0
给定一张无向连通图
若删去其中一个节点和与它相连的所有边之后，这张图分裂成两个或两个以上的不相连的子图，则称 x 为 G 的割点
若删去其中一条边之后，这张图分裂成两个不相连的子图，则称 e 为 G 的桥或割边
Tarjan 大佬做过的贡献：斐波那契堆（毒瘤东西）、Splay Tree（毒瘤东西）、Lint-Cut Tree（已经被踢出考纲的东西）等。。。

时间戳
在图的 dfs 过程中，按照没一个节点第一次被访问的时间顺序进行标记（参照有向图时间戳）

搜索树
参照有向图搜索树（上面有）

追溯值

重要的东西，和有向图有一点点不一样
low[x]定义为以下节点的时间戳的最小值：
1.subtree(x)中的节点 2.通过 1 条不在搜索树上的边能够到达 subtree(x)的节点
初始化：low[x]=dfn[x]
如果在搜索树上 x 是 y 的父节点，$low[x]=min(low[x],low[y])$
如果(x,y)不是搜索树上的边则 $low[x]=min(low[x],dfn[y])$
除了根节点之外，一条边如果不是搜索树上的边，那么这一条边一定能与其他节点构成一个环（树嘛，这个轻轻想想就知道了）

割边判定法则：

无向边(x,y)是桥，当且仅当搜索数上存在 x 的一个子节点 y，满足：

$$dfn[x] < low[y]$$

根据定义 dfn[x] < low[y]说明从 subtree(y)出发，在不经过(x,y)的情况下，是无法达到搜索树上 x 或者是比 x 更早访问的节点的 （如果一条不是搜索树上的边(x,y)（x < y），那么 y 一定在 x 的子树里，所以我访问一定只会访问到比自己 dfn 小的点（大的也会访问但是没用）） 所以若是删去这条边，subtree(y)就好像形成了一个封闭的环境，与节点 x 没有边相连接
读者不难发现：桥一定是搜索树上的边，并且一个简单环中的边一定不是桥
下面的程序求出一张无向图中所有的桥。特别注意：(x,y)是不能用来更新 low 数组的，所以我们可以进行父节点的标记
但是如果这样是处理不了重边的，那么我们考虑，改为记录进入没一个节点的边的编号：
边我们用链式前向星进行存储的时候我们会发现一条是会被记录两次的，所以如果将编号为 i 的边进行了标记，我们还需要将编号为 i^1 的边进行标记

代码：

void tarjan(int x, int in_edge)
{
    dfn[x] = low[x] = ++tim;
    for (int i = head[x]; i; i = e[i].nex)
    {
        if (!dfn[e[i].y])
        {
            tarjan(e[i].y, i);
            low[x] = min(low[x], low[e[i].y]);
            if (dfn[x] < low[e[i].y])
                bridge[i] = bridge[i ^ 1] = 1;
        }
        else if (i != (in_edge ^ 1))
            low[x] = min(low[x], dfn[e[i].y]);
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i, 0);
    for (int i = 1; i < tot; i += 2)
        if (bridge[i])
            cout << e[i ^ 1].y << ' ' << e[i].y << endl;
    return 0;
}

割点判定法则

如果 x 不是搜索树的根节点的话，那么 x 是割点当且仅当搜索树中存在 x 的一个子节点 y，满足：
dfn[x]<=low[y]
特别的，如果 x 是根节点，那么 x 是割点当且仅当搜索树上存在至少两个子节点 y1,y2 满足条件
证明：
**不给，自己证去（模仿割边）**lueluelue
下面给程序体会一下
洛谷板子题 P3388

代码：

void tarjan(int x)
{
    dfn[x] = low[x] = ++tim;
    int flag = 0;
    for (int i = head[x]; i; i = e[i].nex)
    {
        int v = e[i].v;
        if (!dfn[v])
        {
            tarjan(v);
            low[x] = min(low[x], low[v]);
            if (dfn[x] <= low[v])
            {
                flag++;
                if (flag > 1 || x != root)
                    cut[x] = 1;
            }
        }
        else
            low[x] = min(low[x], dfn[v]);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        if (x == y)
            continue;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            root = i, tarjan(i);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (cut[i])
            ans++;
    cout << ans << endl;
    for (int i = 1; i <= n; i++)
        if (cut[i])
            cout << i <<' ';
    return 0;
}

无向图的双连通分量

若一张无向连通图不存在割点，则称它为“点双连通图”，类比，不存在割边即为“边双连通图”
极大点双联通子图被称为点双连通分量简写为“v-DCC”，极大变双联通子图被称为边双连通分量
简称为“e-DCC”
定理：
一张无向图是“点双连通分量”： 1.图的顶点不超过 2 2.图中的任意两点都通是包含在至少一个简单环中，简单环是指不自交的环
“边双连通分量”
当且仅当任意一条边都包含在至少一个简单环中

e-DCC 的求法：

求出无向图中所有的桥，删去

代码：

//加到原来的割边程序
void dfs(int x)
//进行dfs遍历一遍图，不经过桥边和已经被标记过的节点，如果经过桥边那么说明跨越了两个不一样的e-DCC
{
    c[x] = dcc;
    for (int i = head[x]; i; i = e[i].nex)
    {
        int y = e[i].y;
        if (c[y] || bridge[y])
            continue;
        dfs(y);
    }
    return;
}
for (int i = 1; i <= n; i++)
        if (!c[i])
            ++dcc, dfs(i);//dfs遍历

v-DCC 的求法

“点双连通分量”是一个极其容易误解的概念，不能直接删除割点
如果某一个节点是孤立点，则它自己单独构成一个 v-DCC。除了孤立点之外，v-DCC 的大小至少为 2。
虽然桥并不属于任何一个 v-DCC，但是一个割点可能会属于多个 v-DCC。
为了求出“点双连通分量”,我们需要在 Tarjan 算法的过程中维护一个栈，并按照如下的方法维护栈中的元素

1. 当一个节点第一次被访问的时候，把这个节点入栈

2. 当割点判定法则 $dfn[x]<=low[y]$ 成立的时候，无论 x 是否为根，都需要

(1)从栈顶不断弹出节点直至 y 被弹出
(2)被弹出的所有点和 x 一起构成一个 v-DCC

代码：

void tarjan(int x)
{
    dfn[x] = low[x] = ++tim;
    int flag = 0;
    sta[++top] = x;//这是比割点板子多了的一步栈
    if (x == root && !head[x])//孤立点直接跳过
    {
        dcc[++cnt].push_back(x);
        return;
    }
    for (int i = head[x]; i; i = e[i].nex)
    {
        int v = e[i].v;
        if (!dfn[v])
        {
            tarjan(v);
            low[x] = min(low[x], low[v]);
            if (dfn[x] <= low[v])
            {
                cnt++;
                flag++;
                if (flag > 1 || x != root)
                    cut[x] = 1;
                //接下来是进行加入v-DCC的过程
                int y;
                do
                {
                    y = sta[--top];
                    dcc[cnt].push_back(y);
                } while (y != v);
                //跳栈，在第一次搜到就进行跳栈（由于加入栈之后x不一定上面的点就是当前的v所以要从栈顶跳到y之后再加入x节点）（因为一个割点可能同时是很多个V-DCC之中的）
                dcc[cnt].push_back(x);
            }
        }
        else
            low[x] = min(low[x], dfn[v]);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        if (x == y)
            continue;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            root = i, tarjan(i);
    for (int i = 1; i <= cnt; i++)
    {
        cout<<i<<": ";
        for(int j=0;j<dcc[i].size();j++)cout<<dcc[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

v-DCC 的缩点

v-DCC 的缩点比 e-DCC 复杂一点，因为一个割点可能会同时属于多个 v-DCC，设途中 p 割割点和 t 割 v-DCC。我们建立一张包含 p+t 个节点的新图，把每一个 v-DCC 和每一个割点都作为新图中的节点，并在每一个割点与包含他的所有 v-DCC 之间连边，这会构成一棵树

代码：

int num_ed=cnt,new_id[maxn];
    for(int i=1;i<=n;i++)
    {
        if(cut[i])new_id[i]=++num_ed;
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=0;j<dcc[i].size();j++)
        {
            int x=dcc[i][j];
            if(cut[x])
            {
                add_c(i,new_id[x]);
                add_c(new_id[x],i);
            }
        }
    }
    for(int i=1;i<tot_edge;i+=2)
        cout<<edge[i^1].v<<' '<<edge[i].v<<endl;

无向图也写完了

完结撒花